6. 快速排序（重点）🚀
6.1快速排序介绍🚀
快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。
// 假设按照升序对array数组中[begin, end]区间中的元素进行排序 void QuickSort(int* a, int begin, int end) { if(begin >= end) return; // 按照基准值对a数组的 [begin, end]区间中的元素进行划分 int keyi = partion(a, begin, end); // 划分成功后以div为边界形成了左右两部分 [begin, keyi-1] 和 [keyi+1, end] QuickSort(a, begin, keyi-1); // 递归排[begin, keyi-1] QuickSort(a, keyi+1, end);// 递归排[keyi+1, end] }
partion函数就有着这种作用：将选中的keyi位置（keyi一般在开头或结尾的位置）对应的元素为基准，使左边的元素都小于a[keyi]，右边的元素都大于a[keyi]（因为是要升序）
即：
通过这样就能确定key下标对应元素排序之后的位置，因为左边都比其小，右边都比其大，然后通过递归将其左右两个区间分别按照这样的操作来确定元素的位置,当子区间剩下一个元素时就截止，最后得到的就是升序的数据。（看完这个在看看上面的代码）而partion函数有三种，分别是：
- hoare版本
- 挖坑法
- 前后指针法
6.2hoare版本🚀
注：partion函数在这里别名为PartSort1函数
此单趟排序：
- 选一个key。（一般是第一个或者最后一个）
- 单趟排序，要求小的在key左边，大的在key右边
此为key在左边，R先走（key在右边，就需要L先走） 规则解释如下
hoare版本的思路是这样的：我们把最左侧的下标用keyi保存之后，需要让R先出发，遇到比a[keyi]小的元素则需要停下，然后L出发，当L找到比a[keyi]大的元素之后，让R和L对应的元素交换，接着R继续走去寻找比a[keyi]小的元素，重复此步骤直到L和R相遇，相遇之后的所对应的元素一定比a[keyi]对应的数小（下文证明描述），最后将这个相遇时对应的元素与a[keyi]进行交换，更新keyi的位置为相遇位置并返回相遇的位置，至此，此函数结束，新的a[keyi]的左侧数据比它小，右侧数据比它大。
由于L和R不能同时走，因此，相遇有两种情况：1. L撞R，2. R撞L
L撞R：L撞R说明此时R已经停下，而L正在寻找比a[keyi]大的元素，，但R停下的原因就是R找到比a[keyi]小的元素，因此这时候相遇的位置的元素一定比a[keyi]小。
R撞L：R撞L说明此时L已经停下，我们知道，L停下就说明找到了比a[keyi]大的元素,此时R也停下，在R运动之前，二者之间一定会交换，交换后的L对应的元素一定比a[keyi]小，当R继续运动撞上L时，此时相遇的位置对应的元素一定比a[keyi]小。
介绍完之后，看看如下实际步骤：
最终将3与6互换。
PartSort1代码：
//[left. right] int PartSort1(int* a, int left, int right) { int keyi = left; while (left < right)//为了防止错开里面的条件都要加上此条件 { //右边先走，R找小 while (left < right && a[right] >= a[keyi])//一定要把相等的给过滤掉，否则会产生死循环 { --right; } //L找大 while (left < right && a[left] <= a[keyi])//一定要把相等的给过滤掉，否则会产生死循环 { ++left; } if(left < right) Swap(&a[left], &a[right]); } int meeti = left; Swap(&a[left], &a[keyi]); return meeti; }
将其嵌入QuickSort就可以通过逻辑图来看：
由于是二叉树递归实现，当数组有序或接近有序的时候，采用这种方法效率很低，逻辑图会变成这样：
因此，我们需要将这种接近有序的情况也进行处理，使其效率上升，通过改变key的位置从而提升效率。那么key可以如何调整呢，其实key可以随机选一个位置，这样大概率会避免这种情况，但也有可能随机取到的位置就是最左侧或者最右侧的位置，因此也不是足够严谨，通过这一系列的考虑，我们可以利用如下的思想来选择key的位置：
优化选key逻辑：
随机选一个位置做key。
针对有序，选正中间做key。
三数取中。第一个，中间位置，最后一个 选出中间大小的值
上述三个方法均可适用，但为了其通用性以及制定标准，三数取中是不二之选。
三数取中：即将left mid right 三个位置对应的元素进行比较，选择中间大的数的下标给key,再将a[key]与a[left]交换一下，这样，就避免了因有序或者接近有序而造成效率的低下。
三数取中：
int GetMidIndex(int* a, int left, int right)//优化，三数取中 { int mid = left + (right - left) / 2; if (a[left] < a[mid]) { if (a[mid] < a[right]) { return mid; } else if (a[left] > a[right]) { return left; } else//相等情况下，怎样都可以，归为这一类 { return right; } } else // a[left] > a[mid] { if (a[mid] > a[right]) { return mid; } else if (a[left] < a[right]) { return left; } else { return right; } } }
优化后：
//以下均为快速排序涉及的函数 void Swap(int* a, int* b) { int tmp = *a; *a = *b; *b = tmp; } int GetMidIndex(int* a, int left, int right)//优化，三数取中 { int mid = left + (right - left) / 2; if (a[left] < a[mid]) { if (a[mid] < a[right]) { return mid; } else if (a[left] > a[right]) { return left; } else//相等情况下，怎样都可以，归为这一类 { return right; } } else // a[left] > a[mid] { if (a[mid] > a[right]) { return mid; } else if (a[left] < a[right]) { return left; } else { return right; } } } //[left, right] int PartSort1(int* a, int left, int right) { //三数取中 int mid = GetMidIndex(a, left, right); Swap(&a[left], &a[mid]); int keyi = left; while (left < right)//为了防止错开里面的条件都要加上此条件 { //右边先走，R找小 while (left < right && a[right] >= a[keyi])//一定要把相等的给过滤掉，否则会产生死循环 { --right; } //L找大 while (left < right && a[left] <= a[keyi])//一定要把相等的给过滤掉，否则会产生死循环 { ++left; } if(left < right) Swap(&a[left], &a[right]); } int meeti = left; Swap(&a[left], &a[keyi]); return meeti; }
这个之后仍然可以进行优化：小区间优化
通过此递归类似于完全二叉树的结构，想一想由于递归最后三层调用堆栈根据完全二叉树的架构相当于总体的87.5%（从下到上：50%+25%+12.5%），因此，为了节省调用堆栈的空间，可以让最后的这2^3=8个数据用其他排序来代替递归完成，这样就节省了一大半以上的调用堆栈的性能，那么如何改动呢，这里直接在QuickSort函数里面进行修改即可：
void QuickSort(int* a, int begin, int end)//快速排序 { if (begin >= end) { return; } // 由于递归最后三层调用堆栈根据完全二叉树的架构相当于总体的87.5%（50%+25%+12.5%），因此，为了节省调用堆栈的空间，可以让最后的这2^3=8个数据用其他排序来代替递归完成 if (end - begin <= 8) { //随便一个排序都可，这里利用直接插入排序 InsertSort(a + begin, end - begin + 1);//上面有此函数 } else { int keyi = PartSort1(a, begin, end); //[begin, keyi-1] keyi [keyi+1, right] QuickSort(a, begin, keyi - 1); QuickSort(a, keyi + 1, end); } }
挖坑法🚀
注：partion函数在这里别名为PartSort2函数
与hoare版本不同的是，挖坑法的思路是碰到一个就去赋值一个，而不是像hoare中两个都找到进行交换。挖坑法的思路是这样的：
第一步：同样的先进行三数取中避免有序或接近有序，这一点与hoare的思想是一样的，接下来我们用key保存最左侧的值（此值经过这个函数调用结束后就会回到排序后的应有的位置上，即左边比key小，右边比key大，上面的hoare用的是keyi,keyi保存的是下标），并且我们将这个最左侧的位置记录为坑位，用hole = left 保存。
第二步：同样根据右找小，左找大的原则直到相遇，不过具体的行动有所改变。先让右侧的right往左找小，找到之后，就将此值填到坑位，此位置就变成新的坑位，即：hole = right ;接下来左侧的left向右找大，找到之后，将此值填到新的坑位，再将此位置变为坑位：hole = left ，一直到left与right相遇。
第三步：通过前面的步骤，left与right相遇后的位置会变成新的坑位,此时将key保存的数字填入此坑位，此坑位就是数组有序后key的位置。
代码：
void Swap(int* a, int* b) { int tmp = *a; *a = *b; *b = tmp; } int PartSort2(int* a, int left, int right)//2. 挖坑法 { //三数取中 int mid = GetMidIndex(a, left, right); Swap(&a[left], &a[mid]); int key = a[left]; int hole = left;//最左侧初始化坑位 while (left < right) { //右边找小，填到左边坑 while (left < right && a[right] >= key) { right--; } a[hole] = a[right];//找完就填坑 hole = right;//右边就成了新的坑 //左边找大，填到右边坑 while (left < right && a[left] <= key) { left++; } a[hole] = a[left];//找完就填坑 hole = left;//左边就成了新的坑 } a[hole] = key; return hole; }
6.4前后指针法🚀
注：partion函数在这里别名为PartSort3函数
同样最开始是三数取中，然后不同的是前两个版本的方式都是从两侧相向出发，而这个前后指针法则是在同一侧一起出发，那么具体思路是：
定义两个变量cur，prev，这两个变量都作为下标向后运动，让prev = left,cur = left+1,对应前后指针，对于cur这个变量的要求是找比a[keyi]小的数，一旦找到，就先++prev，因为prev是从keyi的位置开始的，而keyi这个位置是循环结束需要进行交换的，因此++prev,然后将a[prev]和a[cur]的值进行交换，再cur++,目的是让比a[keyi]小的数都在左侧，大的都在右侧，直到cur>right截止循环，此时的prev对应的位置就是a[keyi]排序后对应的位置，将a[keyi]的值与a[prev]进行交换，最后返回prev。
执行具体步骤：
PartSort3代码：
int PartSort3(int* a, int left, int right)//3. 前后指针法 { //三数取中 int mid = GetMidIndex(a, left, right); Swap(&a[left], &a[mid]); int keyi = left; int cur = left + 1; int prev = left; while (cur <= right) { //找小 if (a[cur] < a[keyi] && ++prev != cur) { Swap(&a[cur], &a[prev]); } ++cur; } Swap(&a[prev], &a[keyi]);//prev对应的数字一定比key小，可推导，实际上prev对应的一定比key小，cur对应的一定比key大 return prev; }
6.5 快速排序完整代码（递归）🚀
这里我们采用第一种hoare版本的PartSort1进行实现：
//以下均为快速排序包含的函数 void Swap(int* a, int* b) { int tmp = *a; *a = *b; *b = tmp; } int GetMidIndex(int* a, int left, int right)//优化，三数取中 { int mid = left + (right - left) / 2; if (a[left] < a[mid]) { if (a[mid] < a[right]) { return mid; } else if (a[left] > a[right]) { return left; } else//相等情况下，怎样都可以，归为这一类 { return right; } } else // a[left] > a[mid] { if (a[mid] > a[right]) { return mid; } else if (a[left] < a[right]) { return left; } else { return right; } } } //[left. right] int PartSort1(int* a, int left, int right)//1.Hoare版本 { //三数取中 int mid = GetMidIndex(a, left, right); Swap(&a[left], &a[mid]); int keyi = left; while (left < right)//为了防止错开里面的条件都要加上此条件 { //右边先走，R找小 while (left < right && a[right] >= a[keyi])//一定要把相等的给过滤掉，否则会产生死循环 { --right; } //L找大 while (left < right && a[left] <= a[keyi])//一定要把相等的给过滤掉，否则会产生死循环 { ++left; } if(left < right) Swap(&a[left], &a[right]); } int meeti = left; Swap(&a[left], &a[keyi]); return meeti; } //[begin, end] void QuickSort(int* a, int begin, int end)//快速排序 { if (begin >= end) { return; } // 由于递归最后三层调用堆栈根据完全二叉树的架构相当于总体的87.5%（50%+25%+12.5%），因此，为了节省调用堆栈的空间，可以让最后的这2^3=8个数据用其他排序来代替递归完成 if (end - begin <= 8) { //随便一个排序都可，这里利用直接插入排序 InsertSort(a + begin, end - begin + 1); } else { int keyi = PartSort1(a, begin, end); //[begin, keyi-1] keyi [keyi+1, right] QuickSort(a, begin, keyi - 1); QuickSort(a, keyi + 1, end); } }
6.6 快速排序非递归实现🚀
递归的最大问题就是极端场景下，深度太深，会发生栈溢出，因此我们需要用数据结构中的栈来模仿递归过程
非递归实现快速排序，我们就需要用到栈章节中的Stack.h和Stack.c
栈的代码
非递归实现快速排序在思想上是用栈的特性来模拟递归，那么模拟的思路如下：
我们仍然需要上面的partion函数，即PartSort系列中的一个来进行排序，而栈的作用就是用来存储下标区间，想一想递归实现的快速排序，也是先在整体然后切割成一份一份的区间进行一个元素一个元素的排序，非递归也是如此，由于递归采用了先左后右的思想，因此，在栈里面我们也先入右区间再入左区间以便Top时先左后右，先将最左侧的left和最右侧的right进入后，通过一趟排序PartSort3（任意一个都可）能将中间的keyi排序后的位置确定，并返回keyi下标，接下来我们将其看成三部分：
[left, keyi-1]
keyi
[keyi+1,right]
而第二部分已经排好序，因此我们需要将3和1按照先后顺序依次入栈（改变顺序也可以，但为了模仿递归，每次都将按照这个顺序）都入栈之后继续分别将两个区间中的左右赋值给left和right，每个区间就能再分成三个部分，而每一个区间分成之后的第二个部分都会用PartSort3排好序，当区间中的left>=right时就不进行操作，直接进入下一个循环。值得注意的是，这里的非递归的顺序与递归其实是一样的，因为每次先入右区间再入左区间之后，下一次的循环中的left和right都会取出左区间，然后进行StackPop，这样每次执行左右区间一起入栈之后，都会对左区间进行操作，而右区间将保存在栈中，待左区间排好之后，右区间才会开始。
通过递归转化成非递归，相应的操作也会转化成相应的操作：
递归变成循环
递归的返回条件变成循环条件：栈是否为空
来看看具体步骤的结果：
此时会发现除了我们排好的keyi，其他的顺序也发生变化，当然，这是由于PartSort3造成的（PartSort系列的函数的执行结果与功能相同，但执行方式不同，不同的PartSort会对除了keyi以外的顺序产生不同的结果），但这本身也不是我们需要关注的，只要keyi的位置达到我们想要的就足够了
第二次开始之后就是入四个数，分别为右区间和左区间也就是第一部分和第三部分，入之后，左区间的两个值被left和right获取并Pop掉，而右区间的则保存在栈中，通过st->a的指针指向的数为6就能看出0和3已将被Pop掉了，6下面的9由于监视的变量是指针，因此只能看到栈顶的数，不过栈顶为6已经说明了左区间的两个数已经被用过并且Pop掉了。
接下来的步骤同样按照以上的逻辑执行……
快速排序非递归实现： 注：需要引用Stack.c (上面的链接)
void QuickSortNonR(int* a, int begin, int end)//快速排序非递归 { ST st; StackInit(&st); StackPush(&st, begin); StackPush(&st, end); while (!StackEmpty(&st)) { int right = StackTop(&st); StackPop(&st); int left = StackTop(&st); StackPop(&st); /*if (left >= right) 把这个也可以换成下述分别的if，这样可以减少入栈次数 { continue; }*/ int keyi = PartSort3(a, left, right); // [left, keyi-1] keyi [keyi+1, right] if (keyi + 1 < right) { StackPush(&st, keyi + 1); StackPush(&st, right); } //上下两组push顺序调换也可以，不过为了模拟递归的过程，这里仍是先入右区间，再入左区间 if (left < keyi - 1) { StackPush(&st, left); StackPush(&st, keyi - 1); } } StackDestory(&st); }
用队列也能完成，用队列就是以层序遍历的方式进行，模拟不出函数调用堆栈的实际情况，只是访问的顺序不一样，要保持需要的那个顺序，那就要用栈。
快速排序特性：🚀
上面叙述了这么多，但是其特性是一致的，哪怕非递归也是模仿递归思想实现的，因此，我们在这里进行总结:
- 快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序
- 时间复杂度：O(N*logN）
- 空间复杂度：O(logN)
- 稳定性：不稳定
- 在八大排序算法中，快速排序是非常快的也是非常重要的，但是普通的快速排序还没有那么快，快的是优化后的快排，即加上三数取中
对于快速排序，仍有一个库函数qsort可以实现
7.归并排序🚀
7.1 基本思想🚀
介绍：
归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide andConquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。 归并排序核心步骤：
事实上，绿色下方的操作并不存在，而是将归的逻辑展现出来与实际上的递进行联系，有递就有归，对于归并排序，上面的介绍是官方的定义，而下面将是我对于归并排序的理解：
当我们看到归并排序时，就会想到归并的前提，必须是两个有序的数组才能进行归并，而且需要创建新的数组使另两个需要归并的元素进行尾插，就比如合并有序链表利用的就是这个思想。但我们话说回来，对于一组随机顺序的数组将其归并排序，就需要将其分解成两组有序的数组从而进行尾插新数组排序，然而，一个随机数组在不利用其他排序的情况下分解成两个数组使其变成有序是没办法操作的，换句话说就是分成的两个数组不一定是有序的，那么就需要将分解的两个数组分别再分解成两个数组，目的就是让其分解之后的数组有序，才能让这个分解之前的数组通过归并变得有序，这时候我们应都有一个常识：如果一个数组只有一个元素，那么这个数组一定是有序的！ 当然，如果在分解的途中，没有到分解成一个元素时才有序，我们仍然需要分解到一个数组，因为分解的两个数组是否有序是随机的，我们无法进行判断，而如果数组中只有一个元素，那么通过传进去的两个参数begin和end分别代表数组的头和尾，如果begin >= end，那么就说明这个数组只有一个元素，可以return; 到这里，再看看上面的展开图就会发现都是分解到了一个数组只有一个元素之后，才进行归并，（下面的紫色实际上与上部分的红色是重合的，是红色部分的归的步骤，而红色部分是向下递）因此到这里可以看出，采用这种方法是递归实现的。
上面已经提到，归并需要中间新建数组使需要合并的有序数组来进行尾插，最后赋值给原数组。但是递归怎么可以控制新建数组的个数或者确定是同一个数组呢？通过建立递归的子函数就可以实现，即在递归函数中开辟与需要归并数组等大小的数组，在子函数进行递归即可！
7.2 归并排序递归代码🚀
void _MergeSort(int* a, int begin, int end, int* tmp)// 类似于二叉树的后序遍历 { if (begin >= end) { return; } int mid = (end + begin) / 2; // [begin, mid] [mid+1, end] _MergeSort(a, begin, mid, tmp); _MergeSort(a, mid+1, end, tmp); //归并 取小的尾插 //[begin, mid] [mid+1,end] int begin1 = begin, end1 = mid; int begin2 = mid+1, end2 = end; int i = begin; while (begin1 <= end1 && begin2 <= end2) { if (a[begin1] <= a[begin2]) { tmp[i++] = a[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, (end - begin + 1) * sizeof(int)); } void MergeSort(int* a, int n) // 归并排序递归实现 { int* tmp = (int*)malloc(sizeof(int) * n); if (tmp == NULL) { perror("malloc fail"); return; } _MergeSort(a, 0, n - 1, tmp);//子函数递归 free(tmp); tmp = NULL; }
7.3 归并排序特性🚀
对于递归排序，通过介绍中的逻辑图与代码结合可以看出，先遍历左，再遍历右，再合并回去，这与二叉树的后序遍历的逻辑是相同的，并且每次分成两个子数组不是相同就是个数差一个，因此，此结构类似于满二叉树或者是完全二叉树，其高度为logN,而每一行即每一层可以看成成最大数N,因此，其时间复杂度为O(N*logN)。
归并排序特性总结：
归并的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题。
时间复杂度：O(N*logN)
空间复杂度：O(N)
稳定性：稳定
当我们总结到这里之后，不像前面一样就结束了，而是继续讲解归并排序，想到上面的快速排序的递归实现特殊性中或许会由于极端场景导致递归次数太多从而造成栈溢出导致程序崩溃，对于归并排序，由于每次取的都是中间，基本上不会出现栈溢出的现象，然而归并排序的非递归实现仍然需要学习，因为面试可能会叫你手撕非递归，那么接下来看看归并排序的非递归实现：
7.4 归并排序的非递归实现（难点）🚀
上述的快速排序非递归的引出是为了防止出现特殊场合导致栈溢出从而程序崩溃，其中快排的非递归利用了栈，但对于非递归的归并来说，不需要用到栈或者队列，而是像斐波那契数列一样，可以将递归变成循环。
先不考虑一些细节问题，仍然是8个数，将其通过非递归的归并进行排序，那么步骤就是这样：
结合下述代码）不难发现，每一次循环，每组归并的元素数量都乘2，因此，定义一个gap=1,通过每次之后gap *= 2，就可以实现，但问题是，这样分组的归并只有满足元素数量是2的n次幂时才可以进行这样的分组排序，若数组有10个元素，一开始也就是10组，每组一个有序的元素；归并循环一次之后会变成5组，每组两个有序的元素，这一步是可以实现的。然而，当继续归并时，第一组和第二组可以归并，第三组和第四组可以归并，但第五组只有一组就不能归并了我，但按照上图的逻辑，会虚化出第六组，下标的左右区间为begin2和end2将会越界，因此为了避免这样的错误，需要对边界进行处理：
对于两个需要归并的数组，有左边结和右边界，归并两个数组时发生的越界情况，无非有这么三种：
第一组越界：第一组的左区间不可能越界，因为begin1是直接被j赋值，j在for循环条件下永远小于n，因此第一组越界是end1越界，需要break;
第二组全部越界：全部越界代表着begin2也就是第二组的左区间就发生了越界，即begin2>=n，此时也需要break;
第二组部分越界：第二组的部分越界说明右区间的end2越界，但仍然说明有对于相应的第一组来讲，这个第二组可以与之匹配，而归并思想与两个数组中元素的数量无关，只与是否有序有关，因此，这里可以将右区间end2进行修改，让其end2 = n-1,这样就会与之匹配。
再思考一下这样的问题，对于前两种操作的break,虽然不会有错误的操作，但是会不会丢失一些元素归并的步骤呢?答案是不会丢失，这就需要结合具体的代码来看了，因此先展示归并排序非递归的代码：
void MergeSortNonR(int* a, int n)//归并排序非递归 { int* tmp = (int*)malloc(sizeof(int) * n); if (tmp == NULL) { perror("malloc fail"); return; } int gap = 1; while (gap < n) { for (int j = 0; j < n; j += 2 * gap) { //归并 取小的尾插 int begin1 = j, end1 = j + gap - 1; int begin2 = j + gap, end2 = j + 2 * gap - 1; // 第一组越界 if (end1 >= n) { break; } //第二组全部越界 if (begin2 >= n) { break; } //第二组部分越界 if (end2 >= n) { //修正一下end2，继续归并 end2 = n - 1; } int i = j; while (begin1 <= end1 && begin2 <= end2) { if (a[begin1] <= a[begin2]) { tmp[i++] = a[begin1++]; } else { tmp[i++] = a[begin2++]; } } while (begin1 <= end1) { tmp[i++] = a[begin1++]; } while (begin2 <= end2) { tmp[i++] = a[begin2++]; } // 拷贝回原数组 -- 归并哪部分就拷贝哪部分过去 memcpy(a + j, tmp + j, (end2 - j + 1) * sizeof(int)); } gap *= 2; } free(tmp); tmp = NULL; }
即便break,在后面的循环里，最后一步的归并仍然是将两部分合并成一部分，也就是说，这两部分加起来就是所有的元素，不会发生遗漏，此外，这最后一步中，若原数组元素的数量不是2*n的话，一定会发生第二组部分越界，这时候只需要修正一下end2即可，因此第三种情况的修正是至关重要的，会将第一种和第二种情况弥补回来。
8. 计数排序🚀
8.1 基本思想🚀
对于计数排序，其用到了哈希的思想，因此了解这个排序的前提需要理解哈希的思想。
**思想：**计数排序又称为鸽巢原理，是对哈希直接定址法的变形应用。 操作步骤：
即通过定义哈希hash[]数组，将原数组中的值分别计数，最后根据hash的顺序和记录的次数从头到尾释放hash的下标，因为hash的下标就是原数组元素的值
hash数组下标的条件就原数组元素的条件。
- 下标不能为负数
- 下标不能为小数
对于上述的两个条件，小数是无法制约的，也就是说原数组元素如果是小数是没办法利用计数排序的。但对于负数，我们会采取相对映射的方法进行处理。
绝对映射：hash[a[i]]，就是纯粹的值与值对应
相对映射：hash[a[i] + n],相对映射就是由于a[i]的值是负数或者是集中在一起的数，我们就可以将其加上或者减去一个n，让下标变得合理，也就是负数+n变正数从而满足下标；正数-n可以缩小hash开辟的空间
因此，对于哈希思想，相对映射远远好于绝对映射。
8.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* hash = (int*)malloc(sizeof(int)*range); if (hash == NULL) { printf("malloc fail\n"); exit(-1); } memset(hash, 0, sizeof(int) * range); //统计次数 for (int i = 0; i < n; i++) { hash[a[i] - min]++; } //回写 - 排序 int j = 0; for (int i = 0; i < range; ++i) { //出现几次就回写几个i+min while (hash[i]--) { a[j++] = i + min; } } }
8.3 计数排序特性🚀
- 计数排序在数据范围集中时，效率很高，但是适用范围及场景有限。
- 时间复杂度：O(MAX(N,范围))
- 空间复杂度：O(范围)
9.排序特性总结🚀
总结：
对于上述八大排序，有需要掌握递归的，有需要掌握非递归的，有的理解起来很难，但仍有其他类型的排序比如基数排序、猴子排序、桶排序、甚至睡眠排序等等……，但这些排序与八大排序相比来说相差许多，因此，掌握这八大排序足矣！
