2.2 挖坑法
基本思想：
挖坑法对hoare的思想进行了优化。我们设定key数组左边第一个值为坑,右边right找小,找到比key小的值填到坑位，right就成为新的坑位，然后左边left找大,找到后填到坑位上,left此时更新为新的坑位,循环此过程，right接着找小，left找大，交换形成新的坑位，直至left和right相遇。最后把key放到坑里，即类似于hoare版本key应处于的位置。
代码实现：
int QuickSort2(int* arr, int left, int right) //快速排序挖坑法 { int mid = GetMidIndex(arr, left, right); //三数取中 Swap(&arr[left], &arr[mid]);使中间值永远在最左，便于决定谁先走 int hole = left; //对key值保存 int key = arr[left];//保存坑位下标 while (left < right) { while (left < right && arr[right] >= key) //右边找小 { --right; } arr[hole] = arr[right]; //填坑 hole = right; while (left < right && arr[left] <= key) //左边找大 { ++left; } arr[hole] = arr[left];//填坑 hole = left; } arr[hole] = key; //相遇时 return hole; }
相关分析：
需要进行坑位的位置更新
2.3 前后指针法
基本思想：
我们定义两个指针cur和prev，选取key值,cur去遍历小于key的值,对prev++,交换cur与prev值,直至cur遍历完整个数组，prev位置的值一定是比key值小的，即key应处的正确位置
动图展示：
代码实现：
int QuickSort3(int* arr, int left, int right) //前后指针版 { int mid = GetMidIndex(arr, left, right); Swap(&arr[left], &arr[mid]); int key = left; int prev = left, cur = left + 1; //初始化前后指针 while (cur <= right) { if (arr[cur] < arr[key] && ++prev != cur)//逻辑与防止交换同一个位置的元素 { Swap(&arr[cur], &arr[++prev]); } cur++; } Swap(&arr[key], &arr[prev]);//遍历结束将key值放在定位点 return prev; }
相关分析：
++prev!=cur 是对防止同一位置元素进行交换的简单优化，实际中，前后指针法推荐掌握，简单理解易于操控。
对前后指针法的优化：
在数据量极大的情况下，会出现很多相同的数据，此时进行快排，会建立很多栈帧，造成递归深度太深，运行时间过长，对于那些相同的数据我们采用三指针法进行优化
我们定义left，right，cur三个下标，利用cur对序列的遍历，找出大于key，等于key，小于key的三种值，将他们交换到left和right下标位置，将等于key值的数据集中到数组区间中部，然后继续递归剩余的左右区间，直至排序完成。
相关代码：
void _QuickSort3(int* arr, int begin, int end) //前后指针法优化：三指针法 { if (begin >= end) { return; } if ((end - begin + 1) < 15) { InsertSort(arr + begin, end - begin + 1); } else { int mid = GetMidIndex(arr, begin, end); Swap(&arr[begin], &arr[mid]); int key = arr[begin]; int left = begin, right = end, cur = begin + 1; while (cur <= right) { if (arr[cur] < key) { Swap(&arr[left], &arr[cur]); left++; cur++; } else if (arr[cur] > key) { Swap(&arr[cur], &arr[right]); right--; } else//arr[cur]==key时 { cur++; } } QuickSortPlus(arr, begin, left - 1); QuickSortPlus(arr, right + 1, end); } }
2.4 快排非递归版
基本思想：
对于非递归版的实现，因为递归函数在内存实际上是在栈中进行开辟函数栈帧，延用递归中的思想，这里我们采用数据结构中的栈来模拟内存中的栈，从而实现快排的非递归。
代码实现：
void QuickSortNonR(int* arr, 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); int key = QuickSort3(arr, left, right); //排序：利用上面的前后指针法进行排序 // [begin,key-1] [key+1,end] if (key + 1 < right)//key+1==right说明区间只剩一个值时，则可以认为有序 { StackPush(&st, key + 1); StackPush(&st, right); } if (left < key - 1) { StackPush(&st, left); StackPush(&st, key - 1); } } StackDestroy(&st); //栈销毁 }
四、归并排序
1、归并排序递归版
基本思想：
归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。通过递归实现对小数组有序,再返回回来。
动图展示:
代码实现：
void _MergeSort(int* arr, int begin, int end, int* tmp) //归并排序 { if (begin >= end) //只有一个元素或没有元素为有序 { return; } int mid = (begin + end) / 2; _MergeSort(arr, begin, mid, tmp); _MergeSort(arr, mid + 1, end, tmp); //左区间和右区间有序后开始归并 int i = begin; int begin1 = begin, end1 = mid; int begin2 = mid + 1, end2 = end; while (begin1 <= end1 && begin2 <= end2) { if (arr[begin1] <= arr[begin2])//升序 { tmp[i++] = arr[begin1++]; } else { tmp[i++] = arr[begin2++]; } } while (begin1 <= end1) { tmp[i++] = arr[begin1++]; } while (begin2 <= end2) { tmp[i++] = arr[begin2++]; } memcpy(arr + begin, tmp + begin, sizeof(int) * (end - begin + 1));//拷贝回数组arr } void MergeSort(int* arr, int begin, int end) { int* tmp = (int*)malloc(sizeof(int) * (end - begin));//创建暂存数据数组，以保存归并好的数据 _MergeSort(arr, begin, end - 1, tmp); free(tmp);//释放 tmp = NULL; }
相关分析：
归并的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题。
2、递归排序非递归版
基本思想：
因为递归实现过程就是分治,只不过非递归不用递归返回,我们可以不借助其他数据结构，直接对序列进行归并排序，这里主要采用循环：
void MergeSortNonR(int* a, int n) //归并排序非递归版 { int* tmp = (int*)malloc(sizeof(int) * n); if (tmp == NULL) { perror("malloc fail"); exit(-1); } int gap = 1;//定义数组归并距离 //（初始gap为1即每个数组只有一个元素，此时每个数组都为有序数组） while (gap < n)//归并趟次 { for (int i = 0; i < n; i += gap * 2)//分组归并 { //划分区间 int begin1 = i, end1 = i + gap - 1; int begin2 = i + gap, end2 = i + 2 * gap - 1; //判断越界的情况 //这种情况不用考虑归并（已经有序） if (end1 >= n || begin2 >= n) { break; } //这种情况需要归并 if (end2 >= n) { end2 = n - 1; } //归并 int p = i; while (begin1 <= end1 && begin2 <= end2) { if (a[begin1] < a[begin2]) { tmp[p++] = a[begin1++]; } else { tmp[p++] = a[begin2++]; } } while (begin1 <= end1) { tmp[p++] = a[begin1++]; } while (begin2 <= end2) { tmp[p++] = a[begin2++]; } //拷贝排序后数据到原数组 for (int j = i; j <= end2; j++) { a[j] = tmp[j]; } } gap *= 2; } free(tmp);//释放 tmp = NULL;
相关分析：
对于越界情况我们可以直接break掉，拷贝的时候我们只能在for循环里面进行拷贝，也就是部分拷贝，防止在for循环外面进行拷贝的话，arr中会出现随机值的情况。
五、计数排序 - 非比较排序
计数排序基本思想：
统计相同元素出现次数：在排序数组中找到最大最小的数据，算出对应范围（max - min +1）并创建对应长度个数组用来计数（相对位置遍历一次+1），遍历排序数组
根据统计的结果将序列回收到原来的序列中：根据每个出现的数据值与计数数组下标构建的相对映射关系进行统计数据出现次数，最后将统计的出的数据按次序赋值给原数组
我们总共需要遍历三遍数组
动图展示：
代码实现：
void CountSort(int* a, int n) //计数排序 { //遍历找出数组最大最小值（算出范围） int max = a[0], min = a[0]; for (int i = 1; i < n; i++) { if (a[i] > max) max = a[i]; if (a[i] < min) min = a[i]; } int range = max - min + 1; //开辟对应长度个计数数组 int* count = (int*)malloc(sizeof(int) * range); if (count == NULL) { perror("malloc fail"); exit(-1); } //初始化数组计数为0 memset(count, 0, sizeof(int) * range); //遍历计数据出现次数 for (int i = 0; i < n; i++) { count[a[i] - min]++; //a[i] - min：数据与下标构成的相对映射关系 } //排入原数组 int p = 0; for (int i = 0; i < range; i++) { while (count[i]--) { a[p++] = i + min; } } free(count);//释放内存 count = NULL; }
相关分析：
在数据较为集中的情况下，计数排序的性能是很好的，因为N大于range的话，其时间复杂度就是O(N)。缺点是：1、适用于数据集中的情况，数据分散会浪费空间 2、只适用于整型数据的排序
六、对排序的分析总结
什么是排序的稳定性：
如果在某个排序算法在排序过程中，没有打乱原有序列中相同数据的相对位置关系，我们就称这个算法是稳定的。
像是希尔排序，相同的数据可能被预排序到不同的组，不能保证排序的稳定性；像是冒泡排序是从左到右进行比较排序，相同数据的相对位置关系不会发生改变，因此排序是稳定的。
排序算法复杂度及稳定性总结：
思维导图：
总结：总体来说插入排序，选择排序，冒泡排序是低一级水平的排序算法，希尔排序，堆排序，归并排序和快速排序是高一级别的排序各有优缺点，最后计数排序效率非常高，但有一定局限性。
💙欢迎大家批评指正
