4.2快排的优化二：小区间优化
为什么要用小区间优化，最重要的原因就是递归的程度越深，其被分成的数目越多，子问题越多，在此时我们可以利用插入排序进行优化。
代码示例：
void QuickSort4(int* a, int begin, int end) { //子区间相等只有一个值或者不存在那么就是递归结束的子问题 if (begin >= end) return; //小区间直接插入排序控制有序 if (end - begin + 1 <= 10) { 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); } }
五、归并排序的概念
5.1归并排序的基本思想：
基本思想： 归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有 序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。 归并排序核心步骤：
5.2归并排序的动态图：
5.3归并排序的图解：
简而言之就是
小的放在新数组里
先分再归
六、归并排序的递归实现
6.1按照如下归并排序的基本思路实现代码
这是按照[begin, mid] 和[mid + 1, end]区间来划分的
如果是按照[begin, mid - 1]和[mid , end]这样分会分的不均匀，出现[1, 2]的中位数也是1，造成死循环，只要是数是奇数都会出现这种情况。
6.2写一段代码看归并排序的思路：
void _MergeSort(int* a, int begin, int end, int* tmp) { if (begin >= end) { return; } int mid = (begin + end) / 2; //[begin, mid - 1], [mid, end] _MergeSort(a, begin, mid, tmp); _MergeSort(a, mid + 1, end, tmp); printf("归并[%d, %d][%d, %d]\n", begin, mid, mid + 1, end); }
归并排序的具体过程
归并排序的递归搜索树图
归并排序的递归函数代码如下：
//借助子函数 void _MergeSort(int* a, int begin, int end, int* tmp) { if (begin >= end) { return; } int mid = (begin + end) / 2; //[begin, mid - 1], [mid, end] _MergeSort(a, begin, mid, tmp); _MergeSort(a, mid + 1, end, tmp); //printf("归并[%d, %d][%d, %d]\n", begin, mid, mid + 1, end); int begin1 = begin, end1 = mid; int begin2 = mid + 1, end2 = end; int index = begin;//相当于是每一个区间的开始都是begin while (begin1 <= end1 && begin2 <= end2) { if (a[begin1] < a[begin2]) tmp[index++] = a[begin1++]; else tmp[index++] = a[begin2++]; } //如果还有谁没结束，就把谁放tmp的后面 while (begin1 <= end1) tmp[index++] = a[begin1++]; while (begin2 <= end2) tmp[index++] = a[begin2++]; //把tmp里的数拷贝回a数组 //y总是用for循环实现的 memcpy(a+begin, tmp+begin, (end - begin + 1) * sizeof(int)); } void MergeSort(int* a, int n) { int* tmp = (int*)malloc(sizeof(int) * n); assert(tmp); _MergeSort(a, 0, n - 1, tmp); free(tmp); };
七、归并排序的非递归实现以及归并排序的模板
7.1归并排序递归改非递归的思路：
思路：用循环，人为设置一个gap间隙
刚开始gap = 1,后面gap呈2倍增长
直到gap = 数组长度时结束
gap的作用就相当于划分区间了，每次划分完就排序每个区间，排完就拷贝回原数组
递归改非递归思路虽然简单但是区间的边界控制还是很伤脑筋的，和gap有关的区间边界都要控制，原因：gap突变太快了，跟gap有关的全部都存在越界访问的风险，这一点算是递归改非递归的难点，这点需要我们取突破。个人觉得这个有点像希尔排序对插入排序的优化，使用了gap间隙，使效率得到大大的提升，但是两者还是有细微区别的。
7.2归并排序递归改非递归的代码实现：
void MergeSortNonR(int* a, int n) { int* tmp = (int*)malloc(sizeof(int) * n); int gap = 1; while(gap < n) { //间距为gap是一组，两两归并 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; //end1越界，修正 if (end1 >= n) end1 = n - 1; //begin2越界，第二个区间不存在，修正成不存在的区间 if (begin2 >= n) { begin2 = n; end2 = n - 1; } //begin2 ok, end2越界，修正2即可 if (begin2 < n && end2 >= n) end2 = n - 1; // 条件断点 if (begin1 == 8 && end1 == 9 && begin2 == 9 && end2 == 9) { int x = 0; } int index = i; while (begin1 <= end1 && begin2 <= end2) { if (a[begin1] < a[begin2]) tmp[index++] = a[begin1++]; else tmp[index++] = a[begin2++]; } //如果还有谁没结束，就把谁放tmp的后面 while (begin1 <= end1) tmp[index++] = a[begin1++]; while (begin2 <= end2) tmp[index++] = a[begin2++]; } memcpy(a, tmp, n * sizeof(int)); gap *= 2; } free(tmp); }
7.3介绍一种比较好找bug 的调试方法：条件断点法
作用：调试时可以直接使程序停在想要的位置，从而提升调试效率
比如说我们想让程序停在出问题的归并[8, 9][9, 9]这个区域，我们只需写一段代码，然后将断点打在这个位置：
if (begin1 == 8 && end1 == 9 && begin2 == 9 && end2 == 9) { int x = 0; }
7.4归并排序的模板（竞赛用）
#include<iostream> using namespace std; const int N = 100010; int n; int q[N], tmp[N]; void merge_sort(int q[], int l, int r) { if(l >= r) return;// 特判区间内如果只有一个数或者为空时，直接return; int mid = l + r >> 1;//确定分界点mid merge_sort(q, l, mid), merge_sort(q, mid+1, r);//递归排序两边 int k = 0, i = l, j = mid + 1; while(i <= mid && j <= r)//归并，合并两边 if(q[i] <= q[j]) tmp[k++] = q[i++]; else tmp[k++] = q[j++]; while(i <= mid) tmp[k++] = q[i++];//再次查看左边区间是否还有剩余 while(j <= r) tmp[k++] = q[j++];//再次查看右边区间是否还有剩余 for (i = l, j = 0; i <= r; i++, j++) q[i] = tmp[j];//把tmp[i] 存到q[j]里 } int main () { scanf("%d", &n); for(int i = 0; i < n; i++) scanf("%d", &q[i]); merge_sort(q, 0, n - 1); for(int i = 0; i < n; i++) printf("%d ", q[i]); return 0; }
八、两种排序的对比总结
8.1快速排序的特性总结
快速排序的特性总结： 1. 快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序
2. 时间复杂度：O(N*logN)
3. 空间复杂度：O(logN)
4. 稳定性：不稳定
8.2归并排序的特性总结
归并排序的特性总结： 1. 归并的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题。
2. 时间复杂度：O(N*logN)
3. 空间复杂度：O(N)
4. 稳定性：稳定
8.3快速排序的时间、空间复杂度分析（来自书籍）
快速排序的一次划分Parttion算法两头交替搜索，直到两段区间重合，时间复杂度是O（N），整个快速排序的时间复杂度与划分的趟数有关，也就是说，快速排序的时间性能取决于快速排序递归的深度，如果是划分过程比较均匀， 递归树是平衡的，此时性能较好。在最优的情况下，划分Parttion每次都比较均匀，如果排序n个关键字，递归的搜索深度为log（n），这样整个算法的时间复杂度是O(nlogn)的。
如果是在有序的情况下，长度为n的数据表要经过N次划分，此时的时间复杂度为o(N^2)，如果是用三数取中，可以降低其时间复杂度。
快排的空间复杂度分析：从空间性能上看，尽管快速排序需要一个元素的辅助空间，由于快速排序是递归的，每层递归调用时的指针和参数均要栈来存放，存储开销在理想的情况下为O（logN）；在最坏的情况下为O(N)。
另外，快速排序过程中的关键词相同的元素在排序前后相对位置发生了改变，因此，快速排序是不稳定的排序算法。
8.4归并排序的时间、空间复杂度分析
归并排序是分治思想的最典型的例子，上面的算法中，对一组数a[n]进行排序，先将它分为[begin, mid] 和[mid + 1, end]区间来划分的，分别通过递归调用将他们单独排序，最终将有序的子数组归并为最终的排序结果。具有N个记录的序列进行归并排序的递归的深度就是具有n个结点的完全二叉树的深度，可以看出来整个排序归并排序需要进行log(N)次，因此，总的归并排序算法的时间复杂度为O(logN)，而且这是归并排序算法最好、最坏、平均的时间复杂度。
由于归并排序在归并过程中需要与原始记录序列同样数量的存储空间存放归并结果以及递归时深度为logn的栈空间，因此，空间复杂度为O(n + logn)。
非递归的合并排序避免了递归时深度为logn 的栈空间，空间只是用到了申请归并临时用的tmp数组，因此，时间复杂度为O(n),在时间上也有一定的提升，省去了递归拆分，但总体时间复杂度还是O(logn)。应该说，使用归并排序时，尽量考虑非递归的方法。
8.5快速排序和归并排序测试用时
数据量为10万时，不分伯仲（release版本）
数据量为100万时（release版本）
数据量为1000万时（release版本）
