一.插入排序。

1.算法描述：

①.单趟的分析。

整个序列区间为[0,n-1]。在某个单趟中，设需要插入排序的元素下标为(end+1)，则在前面[0,end]的区间里，所有元素有序。此时将要排序的元素抽出，并用tmp储存（因为end会不断变化），随后判断tmp与a[end]的大小，若tmp < a[end]，那么让end所指的元素向后挪一个位置（即a[end+1] = a[end])，然后end--。就这么循环往复，一直到tmp > a[end]为止，此时将tmp插到a[end]后面（a[end+1] = tmp）。

②.整体的分析。

看完对单个元素的插入排序，我们再来关注整个序列所有元素的插入排序。其实只需要配合一个for循环就好,即令end的初始值依次等于a的每一个下标（i）,随后i++,即可实现每个元素的排序。

但需要注意的是，end+1的初始值始终对应的是待排序数 。

2.细小的坑。

①.关于为什么是i < n - 1的问题。

首先下标的区间是[0,n-1]，但为什么i无法取n-1呢？因为在该算法中，要插入的数据,即tmp，所对应的下标，始终是end+1；则需要对序列最后一个元素排序时，其下标为end+1,而end = n - 2(即倒数第二个元素的下标)。同时在代码中，我们始终让end每一趟初始值 = i，以实现for循环的遍历。所以在遍历最后一个元素时，i = n-2。

②.关于else里不插入，反而写break的问题。

我们来讨论一个极端状况，假如待排序数为全场最小，end最终状态为-1，而while的条件是end>=0。如果这个时候在else内执行插入操作，就会导致跳出循环，待排序数没法插入。

3.代码的实现。

void InsertSort(int* a, int n) {//整个序列区间为[0,n-1].[0,end]有序，将end+1所对应元素插入有序区间内。 for (int i = 0; i < n - 1; i++)//因此处理整个序列最后一个元素的排序时，end = n-2,end+1 = n - 1,而i又对应着该趟end的初始值，因此i < n - 1。 { //单趟。 int end = i; int tmp = a[end + 1];//找个值存储将被覆盖的end + 1. while (end >= 0) { if (tmp < a[end]) {//小于就挪，大于就插。 a[end + 1] = a[end]; end--; } else { break;//将插入放在循环外，是为了规避tmp在整个序列里最小，且需要插入排序时，end = -1，出循环，从而没法插入的问题。 } } a[end + 1] = tmp; } }

4.关于复杂度的讨论。

最差：

即逆序的情况，此时挪动次数为1+2+3+...+n-2，即O(N^2)。

最好：

即整个序列顺序的情况，此时无需挪动，只让i不断++就行了，为O(N)。

二.希尔排序。

1.算法描述。

该排序主要对插入排序倒序所造成的费时进行优化，分为两个部分：

①.预排序（让数组先接近有序）。

将序列分成gap个组，每组元素间间隔gap，在遭遇逆序这种极端情况时，大数可以一次挪动gap个位置，而不像插排那样一次只能挪一个位置。

最终序列：

然后在每一个组里进行插入排序,但一定要记得每次自加的数为gap，而非1。最后整个序列相比起倒序更加有序，也就更能减少时间。

②.插入排序。(详情见一)

在进行预排序以后，将所得到的序列进行插入排序，即可得到顺序的序列。

2.算法实现。

①.关于每次移动步数的问题。

其每一组内的排序上其实依旧是插入排序，只是待排序数(tmp)下标的所对应的是end+gap的初始值，毕竟每个元素之间间隔gap而非纯插排中的1。

②.关于如何操控组数的问题。

再在插排外面嵌套一个for循环，循环走gap次即可，同时令内层for循环中i的初始值为j。

单个预排序代码实现：

void ShellSort(int* a, int n) { int gap = 3; for (int j = 0; j < gap; j++)//利用j来调控组数。 { for (size_t 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;//插。 } } }

③.关于选gap的问题。

上面部分的gap是锁死的，但gap的大小会影响排序的效率，且不同序列的gap也不尽相同，所以我们接下来探讨一下gap取何值最合适。

依据大gap和小gap的特点，我们利用while循环与(gap/3) + 1将二者结合,进行多次预排序，gap每进行一次预排序缩小三分之一，大gap保证速度，小gap保证精度，直至最后gap为1，gap为1时进行插入排序。由此实现全部算法全部部分(预排序+插入排序)。

gap/3后加1可保证无论如何，最终gap都能为1，也就是最终都是插排。

最终代码：

void ShellSort(int* a, int n) {//一组一组来。 int gap = n; while (gap > 1) {//进行多次预排序，gap每进行一次预排序缩小三分之一，大gap保证速度，小gap保证精度，直至最后gap为1，gap为1时进行插入排序。由此实现全部算法。 gap = gap / 3 + 1;//+1使得无论如何，最终gap都能为1。 for (int j = 0; j < gap; j++)//利用j来调控组数。 { for (size_t 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;//插。 } } } }

三.选择排序。

1.算法描述。

在序列里每遍历一遍，选出最小的一个，与该趟遍历初始的那个元素进行交换，放到左边。

优化一下，既选最小，也选最大。在begin与end区间内，找到最小数放到最左边(begin)，最大数放到最右边(end)。

2.算法实现。

单轮遍历：

①.找到每一轮遍历的最大最小值。

先设置最大值下标为maxi，最小值下标为mini。将它们初始值都假设为begin，然后利用for循环对后面[begin + 1,end]区间进行遍历，如果满足a[i] > a[maxi],将maxi的值换为i，满足a[i] < a[mini],将mini的值换为i。

②.将每一轮遍历最大最小值放到相应位置。

将已经找到的最大最小值，利用Swap函数与begin或end进行交换，使其到相应位置。

整体：

利用while循环实现多次遍历，每次遍历完以后，记得end--,begin++。

void SelectSort(int* a, int n) { int begin = 0; int end = n-1; while (begin < end)//begin到end间无序，需要找最大最小值 {//最终大的在右，小的在左。 //找最大最小值的下标 int mini = begin; int maxi = begin; for (int i = begin + 1; i <= end; i++) { if (a[i] > a[maxi]) {//i每走一步，最大最小值就更新一下。 maxi = i; } if (a[i] < a[mini]) { mini = i; } } //找到以后将最小值与a[begin]交换，最大值与a[end]交换。 //因为每一轮遍历在区间[begin,end]里，最终状态是a[begin]最小，a[end]最大。 Swap(&a[begin], &a[mini]); Swap(&a[end], &a[maxi]); begin++; end--; } }

3.产生的异常。

该序列很是特殊，首元素就是全序列最大值，即算法执行过程中下标为maxi,第二个元素是全序列最小值，下标为mini；但请别忘了首元素的下标也是begin，在找到最小元素以后会执行交换操作，即首元素与mini所对应元素进行交换，那么1被换到了首元素，这个时候maxi仍旧指向首元素，但最大值9已经被换到了后面，可谓货不对板。

以下为第一轮遍历从开始到swap(begin,mini)的图示：

所以我们在最大元素被换走时应该更新一下maxi。

以下为最终版代码(不要参考上面初版的代码！！！！！)：

void SelectSort(int* a, int n) { int begin = 0; int end = n-1; while (begin < end)//begin到end间无序，需要找最大最小值 {//最终大的在右，小的在左。 //找最大最小值的下标 int mini = begin; int maxi = begin; for (int i = begin + 1; i <= end; i++) { if (a[i] > a[maxi]) {//i每走一步，最大最小值就更新一下。 maxi = i; } if (a[i] < a[mini]) { mini = i; } } //找到以后将最小值与a[begin]交换，最大值与a[end]交换。 //因为每一轮遍历在区间[begin,end]里，最终状态是a[begin]最小，a[end]最大。 Swap(&a[begin], &a[mini]); if (begin == maxi) {//更新一下,防止begin与maxi重叠，导致货不对板。 maxi = mini; } Swap(&a[end], &a[maxi]); begin++; end--; } }

四.快速排序。

1.算法描述。

注意：下面讲的“三分天下”其实是key将序列二分为左右两个区间。

单趟：

动画：

left找比key大，right找比key小，让right先行，找到目标停住，left再行，left找到后，left停住，right的值与left的值互换。在left与right相遇以后，交换该位置与key的元素。

整体：

在单趟完成以后，整个序列可谓三分天下，分为左区间，目标数(a[key])，右区间。然后借用二叉树里学到的递归思想，再将左右区间分别拆开，作为一个新序列，再不断对新序列执行单趟操作，执行完又三分天下，又拆...直到拆到序列只剩一个元素为止。也就是每个单趟key都在二分序列，如果每次单趟的分割都为二分，那么整个递归就可以看成是一棵满二叉树。

2.算法实现。

单趟：

将left和right作为整体递归操作上的序列的左边界和右边界，而在单趟排序里真正行使其效用的是begin和end。

Ⅰ.代码展示（暗藏错误）：

void QuickSort(int* a, int left,int right) {//将left和right作为整体递归操作上的左边界和右边界，而在单趟排序里真正行使其效用的是begin和end。 int begin = left; int end = right; int key = a[begin]; //单趟。 while (begin < end) {//左边找大，右边找小 while(a[end] >= a[key]) { end--; } while(a[begin] <= a[key]) {//左边遇到比key小的就一直遍历，遇到比key大就停止。 begin++; } } //begin和end相遇以后，交换key与当前位置数据。 Swap(&key, &a[begin]); }

在代码实现过程中，end或begin找到目标了，就跳出其各自的while循环，以达到停车的目的。

Ⅱ. left做key，end先走，begin与end的相遇点总是小于key的分析：

Ⅲ.小问题：

①.

在这组数据遍历的过程中，begin与end相遇后，begin还在找比它大的，结果就一脚油门开过了。

所以要给寻找过程的while增加一个begin<end的强制停车条件，无论找没找到比begin大的，遇到这个条件就停下来：

②.

在单趟遍历最后一步，a[begin]即a[5]与a[0](key？)发生交换，交换后a[5]确实为6了，a[0]理应为3，但为什么还是原来的值6呢？

key为一个局部变量，那么它并不会代表序列中的a[0]，它只是一个值，当a[begin]的元素(3)与key(6)交换时，a[begin]的3换给了key，而非a[0],就导致a[0]仍旧为6。就像把钱拿给财务，看似财务老板是一伙的，结果财务跑路了，老板压根没拿到钱。

解决方案：将key变成下标。

③.

在单趟最终排序以后，目标值经过交换，挪到了begin所对应的元素处，此时key也要跟着挪窝，毕竟下标key始终对应着目标值。

单趟最终代码：

void QuickSort(int* a, int left,int right) {//将left和right作为整体递归操作上的左区间和右区间，而在单趟排序里真正行使其效用的是begin和end。 int begin = left; int end = right; int key = begin;//用key存储目标元素的下标！！ //单趟。 while (begin < end) {//左边找大，右边找小 while (begin < end && a[end] >= a[key]) { end--; } while (begin < end && a[begin] <= a[key])//循环里加一个begin < end,防止相遇后不停车。 {//左边遇到比key小的就一直遍历，遇到比key大就停止。 begin++; } //begin和end都找到目标后二者交换。 Swap(&a[begin], &a[end]); key = begin;//交换以后目标值移到了begin,此时key也得挪窝。 } //begin和end相遇以后，交换key与当前位置数据。 Swap(&a[key], &a[begin]); }

Ⅳ.前后指针法。

int PartSort2(int* a, int left, int right) { //三数取中。 int midi = GetMidi(a, left, right); Swap(&a[left], &a[midi]);//把大小中等的数换到最左，不打乱之前的执行步骤。 int prev = left; int cur = left + 1; int key = left; while (cur <= right) { if (a[cur] < a[key] && ++prev != cur)//防止自己和自己交换,同时执行prev++的操作。 { Swap(&a[cur], &a[prev]); cur++; } else { cur++; } } Swap(&a[prev], &a[key]); key = prev; return key; }

整体：

(图请参考上面算法描述的整体部分)

序列未排序前先有left和right两个最左最右的区间边界，待进行一次单趟后，区间三分天下。

“三分天下”的区间：[left,key - 1] key [key + 1,right]。

随后每个单独的区间作为一个新序列，再次三分天下，就这么一直递归，往下分，分到递归停止

递归停止的条件：

此时left = 0,right = 1,a[key] = 2,所以交换后key = 1。带着这些值，我们来分析交换后的区间，区间为[0，0] 1 [2 ，1]，这时就会发现问题，这个小序列压根没有右区间，而且正常区间怎么可能左边大于右边。所以我们可以看出结束的条件是:①.区间[0,0]左右边界相同,即只有一个元素。②.出现不存在的区间[2,1]，即没有右区间。在下一次的单趟中，两个老区间又各自变成了新的序列，并进行单趟，每个新序列中，区间左边界变成了left，右边界变成了right,所以 结束条件可写成：left >= right.(其中left=right 对应①，left > right对应②）

最终代码：

void QuickSort(int* a, int left,int right) {//将left和right代表一个序列的左右区间的边界，而在单趟排序里真正行使其效用的是begin和end。 //递归停止的条件，要么区间只有一个元素（left = right),要么没有单边区间 if (left >= right) { return; } int begin = left; int end = right; int key = left;//用key存储目标元素的下标！！ //单趟。 while (begin < end) {//左边找大，右边找小 while (begin < end && a[end] >= a[key]) { end--; } while (begin < end && a[begin] <= a[key])//循环里加一个begin < end,防止相遇后不停车。 {//左边遇到比key小的就一直遍历，遇到比key大就停止。 begin++; } //begin和end都找到目标后二者交换。 Swap(&a[begin], &a[end]); } //begin和end相遇以后，交换key与当前位置数据。 Swap(&a[key], &a[begin]); key = begin;//交换以后目标值移到了begin,此时key也得挪窝。 //整体，开始递归分治，分为三个区间：[left,key - 1],key,[key + 1,right]。 QuickSort(a,left,key - 1); QuickSort(a,key + 1,right); }

3.复杂度的分析。

因为这种排序的递归类似于满二叉树的递归，所以递归层数(高度)可以看作logN,而每一次单趟中，begin++,end--,它们向中靠拢，最终走的步数之和就是N,所以O(N) = NlogN。

4.当下代码的不足。

递归次数或深度过多过大导致栈溢出。

在遇到已经顺序的序列时，再使用快速排序会出现栈溢出的情况。分析：在算法中，end先行，去寻找比key小的数

递归中每个单趟的开销：

也就是说把二分玩没了，二叉树的框架也没了，所以总开销直接降级成了O(N^2),立马变的跟冒泡一样成路边一条了，同时深度变成了N,如果序列数据过多会使得深度过深，导致栈溢出。

优化方案：

Ⅰ.随机选key，但不靠谱。

Ⅱ.三数取中：

即取序列最左边，最右边以及最中间三个数，在三个数中找一个既不是最大，也不是最小的数作为key。

代码实现：(注意下面的midi,left,right统统指下标，而取中看的是数值大小)

int GetMidi(int* a, int left, int right)//取中数作key,防止顺序栈溢出。 { int midi = (left + right) / 2; if (a[left] < a[midi]) {//那个下标所对应的元素大小在中间，就返回哪个下标。 if (a[midi] < a[right]) { return midi; } else if (a[right] < a[left]) { return left; } else return right; } else//a[left] >= a[midi] { if (a[midi] > a[right]) { return midi; } else if (a[right] > a[left]) { return left; } else return right; } }

使用的时候注意：使用完以后要将大小中等的数换到最左当key，毕竟之前的算法都是建立在最左边的数作为key，每次单趟二分的基础之上。

Ⅲ.小区间优化：

在三数取中完了以后，能够保证每个单趟都可以二分。

快排如果每次单趟的分割都为二分，那么整个递归就可以看成是一棵满二叉树。在学满二叉树的时候，我们知道越接近叶子，该层节点树占总节点数的比例就越大，开销也就越大。

所以我们可以把后几层的递归给去掉，这样总开销就去掉了百分之八十，如何做呢？我们可以打组合技，在遇到区间小的序列时，用插入排序，区间大再递归调用。

代码：

if ((right - left + 1) < 10)//小区间优化，不再递归分割排序，减少递归次数。 { InsertSort(a + left,right - left + 1);//a是整个大序列的地址，找目标小序列的地址，要用a加上小序列的left。 }

5.非递归实现快排。

用递归实现快排，如果深度过大，会造成栈溢出的现象，有没有既能用到递归思想，又不会栈溢出的操作？有的兄弟，有的。我们直接利用栈来模拟实现递归，毕竟栈这个数据结构开辟空间的时候用的是malloc,而这么开辟出来的空间存在堆区，堆区有好几个G的空间，存储空间比存储递归的栈区（只有几兆）要大得多。

栈存在的目的就是为了存储每次递归时的区间。

#include"stack.h" void QuickSortNonR(int* a, int left, int right)//非递归实现快排。 { ST st; STKInit(&st); STKPush(&st,right);//入栈顺序先右后左。可保证出栈先左后右，更能符合递归先左后右 STKPush(&st,left); while (!STKEmpty(&st)) {//单趟。 int begin = STKTopData(&st); STKPop(&st); int end = STKTopData(&st); STKPop(&st); int key = PartSort2(a, begin, end);//执行单趟操作，并取key。 //区间：[begin , key - 1] key [key + 1 , end] //依旧入栈先右后左。 //模拟递归，整体。 if (key + 1 < end) { STKPush(&st, end); STKPush(&st, key + 1); } if (begin < key - 1) { STKPush(&st, key - 1); STKPush(&st, begin); } } }

五.归并排序。

1.底层逻辑。

合并两个有序序列：

a分成两个有序的区间，begin1和begin2比较，将小的那个对应的元素(a[begin])赋值给i，随后赋值给i的begin往后++，就这么一直重复，直到有个序列的begin到end为止。那如果另一个序列还没有到end怎么办？此时就将这个序列的a[begin]赋值给i, 然后++，直到触底为止。

但一个序列是乱序的，该怎么保证它左右区间有序呢？

2.两个流程。

可以利用递归的手法，将序列不断拆解，当拆解到左右区间均只剩一个元素时，就能满足当下小序列左右区间都有序。

拆解完以后，开始从底层向上执行合并的操作，依旧利用递归。当回到序列a时，a一定有序。

3.代码的实现。

递归过程：先左拆解，后右拆解，最后进行合并。类似于后续遍历的顺序。

void _MergeSort(int* a,int* tmp,int begin,int end) { if (begin >= end) { return; } //分解。 int midi = (begin + end) / 2; _MergeSort(a, tmp, begin, midi); _MergeSort(a, tmp, midi + 1, end);//如此划分避免偶数与偶数+1构成的区间造成的死循环。 //归并。 int begin1 = begin; int end1 = midi; int begin2 = midi + 1; int end2 = end; int i = begin; while (begin1 <= end1 && begin2 <= end2) { if (a[begin2] > a[begin1]) { tmp[i++] = a[begin1++];//先tmp[i] = a[begin1]，再i++,begin1++。 } else { tmp[i++] = a[begin2++]; } } while (begin1 <= end1)//右区间走通头，左区间还有。 { tmp[i++] = a[begin1++]; } while (begin2 <= end2)//左区间走通头，右区间还有。 { tmp[i++] = a[begin2++]; } memcpy(a + begin, tmp + begin, sizeof(int) * (end - begin + 1));//注意，每一趟的begin不一定等于0 } void MergeSort(int* a, int n) { int* tmp = (int*)malloc(sizeof(int) * n); if (tmp == NULL) { perror("fail!"); exit(-1); } _MergeSort(a,tmp,0,n - 1);//用子函数来执行递归和归并操作。 free(tmp); }

注意：①.拆分的时候区间一定要写成[begin,midi] [midi + 1,end]!!

②.memcpy里前两个参数。

每次执行归并操作时， 当下序列的初始为begin，并不一定为0，因此memcpy里前两个参数一定要加上begin。

4.非递归实现。

六.Count排序。

1.算法描述。

①.利用count数组统计原数组里数据出现的次数。

原数组里元素的值是几，就在count数组对应下标的元素上++(count里的下标，就代表原数组里元素的值)，出现几次就++几次。

②.排序。

统计完以后，依照下标的自然次序以及出现次数，将count里的下标写回原数组里。

但此时会出现一个问题，假设原数组里的最大的数比较大，但数据总数又比较小，那么按照这个数所开辟的空间count就会有很大的浪费,为了节省，我们可以进行一个相对映射，即count[a[i]-min] 。

2.代码的实现。

void CountSort(int* a, int n) { int min = a[0]; int max = a[0]; for (int i = 1; i < n;i++)//类似于选择排序的找最大最小。 { if (a[i] < min) { min = a[i]; } if (a[i] > max) { max = a[i]; } } int range = max - min + 1; int* count = (int*)calloc(range,sizeof(int));//开辟空间count,并对其初始化。 if (count == NULL) { perror("fail!"); exit(-1); } //统计次数， for (int i = 0; i < n; i++) { count[a[i] - min]++;//相对映射。 }//count[n]就代表n出现的次数。 //排序。 int j = 0; for (int i = 0; i < range; i++) { while (count[i]--) { a[j++] = i + min; } } free(count); count = NULL; }

注意：

七.复杂度和稳定性的对比。

1.稳定性。

稳定性：指值相同的元素，排序前后相对位置不变。

①.直接插入排序

假设tmp一开始在比较的数后面，直接插入排序可以规定tmp与比较的数相同时，插到这个数后一个位置，这样相对位置就不变。所以这种算法稳定。

②.希尔排序

相同数据预排序可能被分到不同组，那么相对位置就变了，就不稳定。

③.选择排序(巨坑！！！)。

规定比a[mini]小的数才进行更新，交换，如果遇到两个相同的比a[mini]小的数，按遍历的优先级，也是前一个被换到begin的位置，因此相对位置没变，稳定了吗？请看下图：

1的相对顺序没变，但6的相对顺序变了。What can I say? 所以不稳定。

④.堆排序

一个堆里全部是相同的数，一顿排序下来，乱成一锅粥...所以一定不稳定。

⑤.冒泡排序

两个值相等可以不交换，所以稳定。

⑥.快排

利用前后指针法， 把这些代入这两句：

可以看出不稳定。

⑦.归并排序

在遭遇上面全是相同值的序列时，begin1的值在前，begin2的值在后，归并时tmp[i]先等于a[begin1]，最后到a[begin2]到tmp里时，依旧begin1在前，begin2在后，所以稳定。

所以综上,涉及Swap(交换位置)或者太复杂的算法，一般都不太稳定。

2.复杂度

快排和归并走的单趟时间开销为N,两种算法利用的递归思想的开销类似于向上调整建堆的深度，因此综合上说是logN,所以总开销是N*logN。

堆排序先建堆后排序，建堆利用向上调整，时间开销为logN，排序利用向下调整,时间开销为N

直接插入排序，最坏为倒序，时间开销为1+2+...+n,即N^2