各种排序方法复杂度总结

　　在C中，排序算法是最基本最常用的算法，不同的排序算法在不同的场景或应用中会有不同的表现，接下来小编搜集了各种排序方法复杂度总结，欢迎查看。

一、冒泡排序

　　主要思路是：

　　通过交换相邻的两个数变成小数在前大数在后，这样每次遍历后，最大的数就“沉”到最后面了。重复N次即可以使数组有序。

　　代码实现

　　void bubble_sort（int arr[]， int len）

　　{

　　for （int i = 0; i < len — 1; i++）

　　{

　　for （int j = len — 1; j >= i; j——）

　　{

　　if （arr[j] < arr[j — 1]）

　　{

　　int temp = arr[j];

　　arr[j] = arr[j — 1];

　　arr[j — 1] = temp;

　　}

　　}

　　}

　　}

　　冒泡排序改进1：

　　在某次遍历中，如果没有数据交换，说明整个数组已经有序，因此通过设置标志位来记录此次遍历有无数据交换就可以判断是否要继续循环。

　　冒泡排序改进2：

　　记录某次遍历时最后发生数据交换的位置，这个位置之后的数据显然已经有序。因此设置标志位记录每次遍历中最后发生数据交换的位置可以确定下次循环的范围。

二、直接插入排序

　　主要思路是：

　　每次将一个待排序的数组元素，插入到前面已排序的序列中这个元素应该在的位置，直到全部数据插入完成。类似扑克牌洗牌过程。

　　代码实现

　　void _sort（int arr[]， int len）

　　{

　　for （int i = 1; i < len; i ++）

　　{

　　int j = i — 1;

　　int k = arr[i];

　　while （j > —1 && k < arr[j] ）

　　{

　　arr[j + 1] = arr[j];

　　j ——;

　　}

　　arr[j + 1] = k;

　　}

　　}