【初阶数据结构】深度解析七大常见排序|掌握底层逻辑与原理（二）https://developer.aliyun.com/article/1617281
3.6.5 挖坑法
void PartSort2(int* a, int left, int right) { if (left >= right) { return; } int midi = GetMidi(a, left, right);//将首位大小取为不大也不小的数 Swap(&a[midi], &a[left]); int keyi = a[left]; int hole = left; int begin = left; int end = right; while (right > left) { while (a[right] >= keyi && right > left)//找小 { right--; } a[hole] = a[right];//移数值 hole = right; while (a[left] <= keyi && right > left)//找大 { left++; } a[hole] = a[left]; hole = left; } a[hole] = keyi; PartSort1(a, begin, hole - 1); PartSort1(a, hole + 1, end); }
跟hoare思想是相同的，在实现方面更加便捷。
过程解析：先将第一个数据存放在临时变量keyi中，形成一个坑位，同样L找大、R找小，当L(或R)停下来时，交换停下位置和当前坑位的数据，并且当前位置形成新的坑位，不断重复该过程，直到L和R相遇，将keyi赋值给该坑位。
3.6.6 前后指针法
void PartSort3(int* a, int begin, int end) { if (begin >= end) { return; } //编译器优化很厉害，可以不使用 if (end - begin + 1 <= 10)//小区间优化 { InsertSort(a + begin, end - begin + 1); } int midi = GetMidi(a, begin, end);//将第一个元素大小取为不大也不小的数 Swap(&a[midi], &a[begin]); int keyi = begin; int prev = begin; int cur = prev + 1; while (cur <= end)//等于也是要换的 { if (a[cur] < a[keyi] && ++prev != cur) { //避免无效交换 Swap(&a[prev], &a[cur]); } cur++; } Swap(&a[prev], &a[keyi]); keyi = prev; PartSort1(a, begin, keyi - 1); PartSort1(a, keyi + 1, end); return 0; }
过程解析:这里使用同相双指针法，具体可以通过动图推导规律。
cur遇到比keyi大的值，++curcur遇到比keyi小的值，++prev，交换prev和cur位置的值，++cur
小总结:
对于不同的方法，单趟的结果都是不一样的。当有多选题时，可以使用不同方式选出答案。对此三个方法，如果需要使用快速排序，推荐使用后面两个方法更快（将两个调用自身函数注释掉，就是单趟排序）。
3.4 归并排序
基本思想:归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法，该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并，得到完全有序序列即先使每个子序列有序，再使子序列间有序。若加你个两个有序表合并成一个有序表，称为二路归并。
实现过程；
void MergeSort(int *a,int n) { int *tmp=(int *)malloc(sizeof(int)*n); if(tmp==NULL) { perror("malloc fail!"); return 1; } _MergeSort(a,0,n-1,tmp); free(tmp) tmp=NULL; } 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);//后序递归 //左边有序 右边有效 合在一起-->合并有序数组问题 int begin1 = begin; int begin2 = 1+ mid; int end1 = mid; int 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));//可能是右边归并 }
过程解析:这里同快速排序使用了分治思想，但是不同于快速排序采用前序遍历根 左子树 右子树，而是采用后序遍历左子树 右子树 根。归并排序主要是通过已有序的子序列合并，得到完全有序的序列。那么将已有序的左右子树得到完全有序的根序列，完成这项操作需要借助一块空间完成合并，再使用内存函数复制或转移到原本序列中。
注意:将合并好序列拷贝到源序列中，如果为右边归并，开头元素下标需要匹配到相对应的位置，只要a+begin和tmp+begin就可以解决这个问题
归并排序的特点总结：
- 归并的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的使解决在磁盘中的外排序问题。
- 时间复杂度: O(N*logN)
- 空间复杂度: O(N)
- 稳定性:稳定
- 没有进行交换，更加适合外排序
3.5 计数排序
计数排序又称为鸽巢原理，是对哈希直接定址法的变形应用。 操作步骤
- 统计相同元素出现次数
- 根据统计的结果将序列回收到原来的序列中
void CountSort(int* a, int n) { int min = a[0], 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)); if (count == NULL) { printf("calloc fail\n"); return; } // 统计次数 for (int i = 0; i < n; i++) { count[a[i] - min]++; } // 排序 int i = 0; for (int j = 0; j < range; j++) { while (count[j]--) { a[i++] = j + min;//加回去 } } }
过程解析:将待排序中数据和新数组中下标对应，并且在记录出现的次数。当数据很大时，很难去把握，因此使用相对映射比较好count[a[i]-min]++;
局限性:
- 不适合分散的数据，更适合集中数据
- 不适合浮点数，字符串、结构体数据排序、只适合整数
计数排序的特性总结：
- 计数排序在数据范围集中时，效率很高，但是适用范围及场景有限。
- 时间复杂度：O(MAX(N,范围))
- 空间复杂度：O(范围)
四、排序算法复杂度及稳定性分析
