挖坑法
1.基本介绍：
挖坑法是基于Hoare的，他通过挖坑的方法避免了R和L相遇时的值一定小于key值的问题，因为不是所有人都能理解为什么R和L相遇时的值是小于key值的。但是像Hoare一样，它也需要根据key值的选定来决定是R先走还是L先走。
挖坑法一开始会取出key值，然后R移动找到比key值小的值，把这里的值填到L的位置上，随后L开始移动，找到比key值大的值填到R的位置上，然后R又开始移动，重复上述步骤，直到R和L相遇，最后把key值填入。
2.代码：
void QuickSortPit(int* a, int begin, int end) { // 当只有一个数据或数列不存在时 if (begin >= end) return; int left = begin; int right = end; int key = a[left]; int pit = left; while (left < right) { // 右边先走，找比key值小的值 while (left < right && a[right] >= key) { right--; } a[pit] = a[right]; pit = right; // 左边再走，找比key值大的值 while (left < right && a[left] <= key) { left++; } a[pit] = a[left]; pit = left; } a[pit] = key; QuickSortPit(a, begin, pit - 1); QuickSortPit(a, pit + 1, end); }
3.时间复杂度与空间复杂度：
核心思想并没有什么变化，换汤不换药，所以时间复杂度与Hoare版本是一样的。
4.图示：
前后指针版本
1.基本介绍：
这个是Hoare的一种变形，还是取一个key值，然后取prev和cur分别指向第一个元素和第二个元素，然后cur向后移动，遇到比key小的值，cur的值就和prev的值交换，遇到比key大的值cur就继续走。这样prev就两种情况与cur在同一位置，或者是停留在值比key值大的位置上，最后cur走到end后，就把prev与key交换，这样也就完成了左右子序列区分的任务。
这是一种Hoare的变形，过程不容易理解，但是代码容易实现。
2.代码：
void QuickSortPoint(int* a, int begin, int end) { if (begin >= end) return; int keyI = begin; int prev = begin; int cur = begin + 1; while (cur <= end) { // 找到比key小的值时，与prev++位置交换，小的向前移动，大的向后移动 if (a[cur] < a[keyI] && ++prev != cur) { int tmp = a[prev]; a[prev] = a[cur]; a[cur] = tmp; } cur++; } int tmp = a[prev]; a[prev] = a[keyI]; a[keyI] = tmp; keyI = prev; QuickSortPoint(a, begin, keyI - 1); QuickSortPoint(a, keyI + 1, end); }
3.时间复杂度与空间复杂度：
时间复杂度与空间复杂度仍旧与Hoare版本的一样。
4.图示
非递归实现
首先我们要知道一个点，每次递归都会开辟一次栈帧空间，而栈帧空间有一个特点就是先开辟的空间最后销毁，但是这也造成了一个问题，如果递归层度过深就会栈溢出。但是快排又依赖于这一先入栈后销毁的特性完成排序。所以我们要实现非递归的快排就需要实现这一特性，而在我们的数据结构中恰好有一个栈的数据结构是具备这种特性的，所以如果我们要非递归实现快排，就要使用栈这个数据结构。
Hoare版本
int Hoare(int* a, int begin, int end) { int left = begin, right = end; int keyI = left; while (left < right) { // 右边先走，找小于key值的值 while (left < right && a[right] >= a[keyI]) right--; // 左边后走，找大于key值的值 while (right < right && a[left] <= a[keyI]) left++; int tmp = a[left]; a[left] = a[right]; a[right] = tmp; } int tmp = a[left]; a[left] = a[keyI]; a[keyI] = a[left]; keyI = left; return keyI; } void QuickSortNonR(int* a, int begin, int end) { // 创建、初始化栈，将begin、end插入栈中 Stack st; StackInit(&st); StackPush(&st, begin); StackPush(&st, end); // 栈非空就循环 while (!StackEmpty(&st)) { int right = StackTop(&st); StackPop(&st); if (StackEmpty(&st)) break; int left = StackTop(&st); StackPop(&st); if (StackEmpty(&st)) break; int keyI = Hoare(a, left, right); if (keyI + 1 < right) { StackPush(&st, keyI + 1); StackPush(&st, right); } if (left < keyI - 1) { StackPush(&st, left); StackPush(&st, keyI - 1); } } StackDestroy(&st); }
挖坑法
int Pit(int* a, int begin, int end) { int left = begin; int right = end; int key = a[left]; int pit = left; while (left < right) { // 右边先走，找比key值小的值 while (left < right && a[right] >= key) { right--; } a[pit] = a[right]; pit = right; // 左边再走，找比key值大的值 while (left < right && a[left] <= key) { left++; } a[pit] = a[left]; pit = left; } a[pit] = key; return pit; } void QuickSortNonR(int* a, int begin, int end) { // 创建、初始化栈，将begin、end插入栈中 Stack st; StackInit(&st); StackPush(&st, begin); StackPush(&st, end); // 栈非空就循环 while (!StackEmpty(&st)) { int right = StackTop(&st); StackPop(&st); if (StackEmpty(&st)) break; int left = StackTop(&st); StackPop(&st); if (StackEmpty(&st)) break; int keyI = Pit(a, left, right); if (keyI + 1 < right) { StackPush(&st, keyI + 1); StackPush(&st, right); } if (left < keyI - 1) { StackPush(&st, left); StackPush(&st, keyI - 1); } } StackDestroy(&st); }
前后指针版本
int Point(int* a, int begin, int end) { int keyI = begin; int prev = begin; int cur = begin + 1; while (cur <= end) { // 找到比key小的值时，与prev++位置交换，小的向前移动，大的向后移动 if (a[cur] < a[keyI] && ++prev != cur) { int tmp = a[prev]; a[prev] = a[cur]; a[cur] = tmp; } cur++; } int tmp = a[prev]; a[prev] = a[keyI]; a[keyI] = tmp; keyI = prev; return keyI; } void QuickSortNonR(int* a, int begin, int end) { // 创建、初始化栈，将begin、end插入栈中 Stack st; StackInit(&st); StackPush(&st, begin); StackPush(&st, end); // 栈非空就循环 while (!StackEmpty(&st)) { int right = StackTop(&st); StackPop(&st); if (StackEmpty(&st)) break; int left = StackTop(&st); StackPop(&st); if (StackEmpty(&st)) break; int keyI = Point(a, left, right); if (keyI + 1 < right) { StackPush(&st, keyI + 1); StackPush(&st, right); } if (left < keyI - 1) { StackPush(&st, left); StackPush(&st, keyI - 1); } } StackDestroy(&st); }
快排的优化
三值取中
我们之前提到过，如果每次key值的位置恰好在最边上，那么快排的的时间效率就会变成O(n2)，虽然这样的概率很小，但是还是有概率会出现。这时我们可以采用三值取中法来避免这种的情况发生。因为key值是影响划分次数的关键，三值取中，就是找到首、中、尾三个位置的值，比较大小，将中间大小的值与key值交换，这样就能保证key值的位置不会是在最边上。
int GetMidIndex(int* a, int begin, int end) { int mid = (begin + end) / 2; if (a[begin] < a[mid]) { if (a[mid] < a[end]) { return mid; } else if (a[begin] > a[end]) { return begin; } else { return end; } } else // a[begin] > a[mid] { if (a[mid] > a[end]) { return mid; } else if (a[begin] < a[end]) { return begin; } else { return end; } } }
小区间优化
每一层的递归都会以2倍数进行增长，即1,2,4,8,16……，通过这个数列我们可以发现，在逻辑上只要我们减少一层递归，就能减少约一半的递归次数。所以我们可以结合其他排序，进行一个判断，在只有多少数的时候就采用其他排序，这样就能有效的避免递归过深。
void QuickSort(int* a, int begin, int end) { if (begin >= end) { return; } if ((end - begin + 1) < 15) { // 小区间用直接插入替代，减少递归调用次数 InsertSort(a + begin, end - begin + 1); } else { int keyi = PartSort3(a, begin, end); // [begin, keyi-1] keyi [keyi+1, end] QuickSort(a, begin, keyi - 1); QuickSort(a, keyi + 1, end); } }
归并排序
递归实现
- 基本介绍：
归并排序是建立在归并操作上的一种有效的排序算法，它采用了分治的思想。将已经有序的子序列合并，得到完全有序的序列。即先使每个子序列有序，然后合并成一个有序的序列。将两个有序表合并成一个有序表叫做二路归并。归并排序需要先分解，在合并。
- 代码：
void _MergeSort(int* a, int begin, int end, int* tmp) { if (begin >= end) return; int mid = (begin + end) / 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, sizeof(int)*(end - begin + 1)); } void MergeSort(int* a, int n) { int* tmp = (int*)malloc(sizeof(int)*n); if (tmp == NULL) { perror("malloc fail"); exit(-1); } _MergeSort(a, 0, n - 1, tmp); free(tmp); tmp = NULL; }
- 时间复杂度与空间复杂度：
归并排序有点类似二叉树结构，高度O(logn)，每层循环n次，所以时间复杂度O(n*logn)；
归并排序额外开辟了n个空间加上递归的logn，所以空间复杂度为O(n+logn），但是logn是可以忽略掉的，最后的复杂度为O(n)。 - 图示：
非递归实现
基本介绍：
归并排序的非递归算法并不需要借助栈这个数据结构来实现，如果使用了栈反而会非常的麻烦，我们只需要控制每次参与合并的元素个数即可，最终便能使序列变为有序。
但是我们需要考虑到一些特殊情况，因为归并是两两归并的，也就是它归并的元素个数是1,2,4,8,16……这样增长的，那么如果元素个数不是这样标准的倍数呢？这时就会有三种情况。
①：最后一个分组中，右侧区间元素个数不够，此时我们合并序列，就需要对这个区间的边界进行控制；
②：最后一个分组中，右侧区间没有元素，就是元素刚好只够左侧区间，那么我们就不需要对这个分组进行合并，因为它本身已经是有序的了；
③：最后一个分组中，左侧区间的元素个数不够，那么我们就不需要对该小组进行合并了。
代码：
void MergeSortNonR(int* a, int n) { int* tmp = (int*)malloc(sizeof(int)*n); if (tmp == NULL) { perror("malloc fail"); exit(-1); } // 归并每组数据个数，从1开始，因为1个认为是有序的，可以直接归并 int rangeN = 1; while (rangeN < n) { for (int i = 0; i < n; i += 2 * rangeN) { // [begin1,end1][begin2,end2] 归并 int begin1 = i, end1 = i + rangeN - 1; int begin2 = i + rangeN, end2 = i + 2 * rangeN - 1; int j = i; // end1 begin2 end2 越界 // 修正区间 ->拷贝数据 归并完了整体拷贝 or 归并每组拷贝 if (end1 >= n) { end1 = n - 1; // 不存在区间 begin2 = n; end2 = n - 1; } else if (begin2 >= n) { // 不存在区间 begin2 = n; end2 = n - 1; } else if (end2 >= n) { end2 = n - 1; } while (begin1 <= end1 && begin2 <= end2) { if (a[begin1] <= a[begin2]) { tmp[j++] = a[begin1++]; } else { tmp[j++] = a[begin2++]; } } while (begin1 <= end1) { tmp[j++] = a[begin1++]; } while (begin2 <= end2) { tmp[j++] = a[begin2++]; } } // 也可以整体归并完了再拷贝 memcpy(a, tmp, sizeof(int)*(n)); rangeN *= 2; } free(tmp); tmp = NULL; }
计数排序
- 基本介绍：
计数排序又称为鸽巢排序，是对哈希直接定址法的变形应用，是一种非比较排序。它先统计相同元素出现的次数，然后根据统计的结果将序列回收到原来的序列中。
计数排序适用于数据范围集中的序列，此时效率很高，但是适用的范围及场景受到限制。 - 代码：
void CountSort(int* a, int n) { int max = a[0], min = 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* countA = (int*)calloc(range, sizeof(int)); if (NULL == countA) { perror("calloc fail\n"); exit(-1); } // 统计次数 for (int i = 0; i < n; i++) countA[a[i] - min]++; // 排序 int k = 0; for (int j = 0; j < range; j++) { while (countA[j]--) a[k++] = j + min; } free(countA); }
- 时间复杂度与空间复杂度：
它的时间复杂度和空间复杂度都是由它自身元素的区间跨度决定的，时间复杂度是O(MAX(n,范围))，空间复杂度是O(范围)。 - 图示：
排序算法复杂度及稳定性分析
不同算法的运行效率
数据过大可能会导致栈溢出，所以选择非递归的快排和归并排序来测试。
void TestOP() { srand(time(0)); const int N = 50000; int* a1 = (int*)malloc(sizeof(int) * N); int* a2 = (int*)malloc(sizeof(int) * N); int* a3 = (int*)malloc(sizeof(int) * N); int* a4 = (int*)malloc(sizeof(int) * N); int* a5 = (int*)malloc(sizeof(int) * N); int* a6 = (int*)malloc(sizeof(int) * N); int* a7 = (int*)malloc(sizeof(int) * N); int* a8 = (int*)malloc(sizeof(int) * N); for (int i = 0; i < N; ++i) { a1[i] = rand(); a2[i] = a1[i]; a3[i] = a1[i]; a4[i] = a1[i]; a5[i] = a1[i]; a6[i] = a1[i]; a7[i] = a1[i]; a8[i] = a1[i]; } int begin1 = clock(); InsertSort(a1, N); int end1 = clock(); int begin2 = clock(); ShellSort(a2, N); int end2 = clock(); int begin3 = clock(); SelectSort(a3, N); int end3 = clock(); int begin4 = clock(); HeapSort(a4, N); int end4 = clock(); int begin5 = clock(); BubbleSort(a5, N); int end5 = clock(); int begin6 = clock(); QuickSortNonR(a6, 0, N - 1); int end6 = clock(); int begin7 = clock(); MergeSortNonR(a7, N); int end7 = clock(); int begin8 = clock(); CountSort(a8, N); int end8 = clock(); printf("InsertSort:%d\n", end1 - begin1); printf("ShellSort:%d\n", end2 - begin2); printf("SelectSort:%d\n", end3 - begin3); printf("HeapSort:%d\n", end4 - begin4); printf("BubbleSort:%d\n", end5 - begin5); printf("QuickSort:%d\n", end6 - begin6); printf("MergeSort:%d\n", end7 - begin7); printf("CountSort:%d\n", end8 - begin8); free(a1); free(a2); free(a3); free(a4); free(a5); free(a6); free(a7); free(a8); }
