排序

插入排序（最有价值）

类似于摸牌

InsertSort：O(N^2)；最好：O(N)

最坏情况：逆序有序

最好情况：O(N)顺序有序

比冒泡排序实际应用更高效

以下是单趟排序，实现多趟需要再嵌套一个for循环，控制end的初值由0到n-1

void PrintArray(int* a, int n)
{for (int i = 0; i < n; i++){printf("%d ", a[i]);}printf("\n");
}// 时间复杂度：O(N^2) 逆序
// 最好的情况：O(N)  顺序有序
void InsertSort(int* a, int n)
{// [0, end] end+1for (int i = 0; i < n - 1; ++i){int end = i;int tmp = a[end + 1];while (end >= 0){if (tmp > a[end]){a[end + 1] = a[end];--end;}else{break;}}a[end + 1] = tmp;}
}

冒泡排序：

BubbleSort：O(N^2)；最好：O(N)

最好情况：O(N)，包含标志位即可实现，表示第一次就没有发生交换，也就是说前一个总比后一个大，结束

先选出一个最大的，交换到最后一个位置。

第一个数进行n-1次交换，也就是小于n次交换，n-j（j=0）

第二个数进行n-2次交换，也就是小于n-1次交换，n-j（j=1）

第n个数进行n-n次交换，也就是小于n-（n-1）次交换，n-j（j=n-1）

void Swap(int* p1, int* p2)
{int tmp = *p1;*p1 = *p2;*p2 = tmp;
}void BubbleSort(int* a, int n)
{for (int j = 0; j < n; j++){bool exchange = false;for (int i = 1; i < n - j; i++){if (a[i - 1] > a[i]){Swap(&a[i - 1], &a[i]);exchange = true;}}if (exchange == false)break;}//for (int i = 0; i < n-1; i++)//{//	if (a[i] > a[i+1])//	{//		Swap(&a[i], &a[i+1]);//	}//}
}

希尔排序

类似于插入排序，但是存在gap的间隔

ShellSort：平均O(N^1.3)

以上是分组排序，可以替换成多组并排

gap随着n进行变化

越到后面的每一次都可能比设想小，不能完全按逆序去算，因为前面已经排过了

最后一轮，gap=1，同时已经非常接近有序了。累计挪动大约n次

void ShellSort(int* a, int n)
{int gap = n;// gap > 1时是预排序，目的让他接近有序// gap == 1是直接插入排序，目的是让他有序while (gap > 1){//gap = gap / 2;gap = gap / 3 + 1;//+1可以保证最后一次一定是1for (int i = 0; i < n - gap; ++i){int end = i;int tmp = a[end + gap];while (end >= 0){if (tmp < a[end]){a[end + gap] = a[end];end -= gap;}else{break;}}a[end + gap] = tmp;}}/*for (int j = 0; j < gap; ++j){for (int i = j; i < n-gap; i += gap){int end = i;int tmp = a[end + gap];while (end >= 0){if (tmp < a[end]){a[end + gap] = a[end];end -= gap;}else{break;}}a[end + gap] = tmp;}}*/
}

直接选择排序

Selectsort：O(N^2)；最好：O(N^2)

最小的和左边换，最大的和右边换

void SelectSort(int* a, int n)
{int begin = 0, end = n - 1;while (begin < end){int mini = begin, maxi = begin;for (int i = begin + 1; i <= end; ++i){if (a[i] < a[mini]){mini = i;}if (a[i] > a[maxi]){maxi = i;}}//循环结束后mini是更新出来的最小的数值//max是最大的Swap(&a[begin], &a[mini]);//如果最大的值和最小的值是两个互换的位置，begin大和end小//min（end）和begin互换后，此时begin是最小的值，但是max存的是begin位置为最大值if (maxi == begin){//为了检测上一个交换的原位置是不是最大值//如果是最大值，则找最大值的新位置，也就是minimaxi = mini;}Swap(&a[end], &a[maxi]);++begin;--end;}
}

堆排序：

HeapSort：O(N*logN)

void AdjustDown(int* a, int size, int parent)
{int child = parent * 2 + 1;while (child < size){// 假设左孩子小，如果假设错了，更新一下if (child + 1 < size && a[child + 1] > a[child]){++child;}if (a[child] > a[parent]){Swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}// 升序
void HeapSort(int* a, int n)
{// O(N)// 建大堆for (int i = (n - 1 - 1) / 2; i >= 0; --i){AdjustDown(a, n, i);}// O(N*logN)int end = n - 1;while (end > 0){Swap(&a[0], &a[end]);AdjustDown(a, end, 0);--end;}
}

快速排序：

有序情况下，快排很吃亏。因为快排的key选的是第一个数，在有序情况下，导致划分出的两个子序列长度极度不均衡，一个子序列可能只包含一个元素（即key本身），而另一个子序列包含了几乎所有剩余元素。以下有优化算法解决这个问题

越接近二分，快排越快

QuickSort：

思想：

选一个关键字key，一般都是第一个数。

一个L，找比key大的，一个R，找比key小的。找到了就交换一下。相等的在哪都行，不用LR交换，否则死循环

然后将比key小的放左边，比key大的放右边

L和R相遇之后，和key交换，划分大小两边的分界线

注意：

为什么相遇位置比key小？因为右边先走

相遇有两种情况：

R遇见L。说明R没有找到比key小的，直到遇到L

L遇见R。R先走，找到小的停下来了。同时L没有找到比key大的，都比key小，直到遇到R

如果L先走就保证不了，因为L找大，以找大为前提的话，相遇位置可能是比key大的

所以：左边做key，R先走。右边做key，L先走（三数选中就不会出现这种情况，不可能存在一边的是=数都比key大或者小）

while循环，在循环体内自增到不满足循环体的条件之后还会走完这个循环，就出现错误，所以要在循环体内部，也就是自增的这个循环加上控制条件

交换的时候不能和key交换，如果和key交换代表着数组和一个局部变量换位置了，并没有改变数组里的数字，所以要写成和a[keyi]交换

left不能从key+1开始，要从key开始比较，否则会出现以下情况：

这种写法坑很多的同时，在有序排列还会很不占优势：

优化算法：

三数取中值法选key：

int GetMidi(int* a, int begin, int end)
{int midi = (begin + end) / 2;// begin end midi三个数选中位数，也就是不大不小的值if (a[begin] < a[midi]){if (a[midi] < a[end])return midi;else if (a[begin] > a[end])return begin;elsereturn end;}else{//...类似的两两比较，选中位数}
}void QuickSort(int* a, int begin, int end)
{if (begin >= end)return;int midi = GetMidi(a, begin, end);//这里还是选择了最左边的值作为key，选哪都可以//然后再选出中间大小的值当做下面算法里的keySwap(&a[midi], &a[begin]);int left = begin, right = end;int keyi = begin;while (left < right){// 右边找小while (left < right && a[right] >= a[keyi]){--right;}// 左边找大while (left < right && a[left] <= a[keyi]){++left;}Swap(&a[left], &a[right]);}Swap(&a[left], &a[keyi]);keyi = left;// [begin, keyi-1] keyi [keyi+1, end]QuickSort(a, begin, keyi - 1);QuickSort(a, keyi + 1, end);
}