详解八大排序（六）------（三路划分，自省排序，归并排序外排序）

1. 快排之三路划分

1. 1 三路划分的诞生由来

通过详解八大排序（三）------（快速排序）的介绍。我们可以知道，决定快排性能的关键是key的寻找：若是每次寻找的key都能将数组二分之一，那么快排的性能最佳；若是每次寻找的key都是将数组分成 1 和 N-1 个数，那么快排的时间复杂度就是O(N^2)。
通过 前后指针 和 寻找随机key 我们可以解决绝大部分数组的找key需求。但是也会有一小部分的数组需求没有实现。
例如：

在面对含有大量重复数据的数组时，hoare版本 和 lomuto版本 的性能都有一定程度的退化。而三路划分是针对大量重复数据的找key方法。

1. 2 三路划分的具体思路

三路划分的核心思路可以理解为 hoare版本 和 lomuto版本 的结合：将数组划分成三个区域，比key小的区域A，等于key的区域B，大于key的区域C。
通过左右指针的方式，将小于key的数放进区域A，大于key的数放进区域C。
再对区域A和C进行划分。直到全部划分完成。

具体的实现思路：

1. key默认取left位置的值。

2. left指向区间最左边，right指向区间最后边，cur指向left+1位置。
   

3. cur遇到比key小的值后跟left位置交换，换到左边，left++，cur++。

例如上面的数组，由于1 < 6，所以1换到6的位置上。

一直重复，直到 left 交换完。得到：

4. cur遇到比key大的值后跟right位置交换，换到右边，right-- 。

接着以上述数组举例。左边数组交换完成，接着交换右边数组：

重复交换，得到：

5. cur遇到跟key相等的值后，cur++。

6. 直到cur > right结束

最终得到：

这样就将数组分成了三个区域。

1. 3 代码实现

//三路划分
void ThreeWaySort(int* arr, int left, int right)
{if (left >= right){return;}//取一个随机值当keyint randi = left + (rand() % (right - left + 1));Swap(&arr[left], &arr[randi]);int key = arr[left];int cur = left + 1;int begin = left,end = right;while (cur <= right){if (arr[cur] < key){Swap(&arr[left++], &arr[cur++]);}else if (arr[cur] > key){Swap(&arr[cur], &arr[right--]);}else {cur++;}}ThreeWaySort(arr, begin, left - 1);ThreeWaySort(arr, right + 1, end);
}

2. 快排之自省排序

2. 1 自省排序的目的

自省排序的诞生和三路划分相似，都是原有的排序在面对新的问题时，出现效率不足的情况。
三路划分面对数组中含有大量重复数据的情况，具有显著的性能提升。但是在其他情况下就很一般，同时三路划分相比一般的快排具有一定的损耗。
这个时候就有自省排序的出现。

2. 2 自省排序的思路

自省排序的本质很简单。就是通过一个深度检测器—可以理解为当前排序的时间复杂度检测器。判断当前快排的深度有没有超过logn。超过了就说明当前排序的效率是有问题的。然后接下来过程就不再使用快排，而是使用堆排序进行排序。

2. 3 自省排序的实现代码

void AdJustDown(int* arr,int sz,int parent)
{int child = parent * 2 + 1;while (child < sz){if (child + 1 < sz && arr[child + 1] > arr[child]){++child;}if (arr[child] > arr[parent]){Swap(&arr[child], &arr[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}void HeapSort(int* arr, int sz)
{for (int i = (sz - 1 - 1) / 2; i >= 0; --i){AdJustDown(arr, sz, i);}int end = sz - 1;while (end > 0){Swap(&arr[0], &arr[end]);AdJustDown(arr, end, 0);--end;}
}void InsertSort(int* arr, int sz)
{for (int i = 1; i < sz; i++){int end = i - 1;int tmp = arr[i];while (end >= 0){if (tmp < arr[end]){arr[end + 1] = arr[end];--end;}else {break;}}arr[end + 1] = tmp;}
}void IntroSort(int* arr,int left,int right,int depth,int defaultDepth)
{if (left > right){return;}if (right - left + 1 < 16)//当需要排序的数据总数小于16，就可以使用选择排序，这时这个排序的效率是最高的{InsertSort(arr + left,right - left + 1);return;}if (depth > defaultDepth)//深度检测器。深度大于一定程度，调用堆排序{HeapSort(arr + left, right - left + 1);return;}depth++;int begin = left, end = right;int randi = left + (rand() % (right - left + 1));Swap(&arr[left], &arr[randi]);//随机数取keyint prev = left, cur = prev + 1;int keyi = left;while (cur <= right){if (arr[cur] < arr[keyi] && ++prev != cur){Swap(&arr[cur], &arr[prev]);}++cur;}Swap(&arr[prev], &arr[keyi]);keyi = prev;//使用的是lomuto版本的快排IntroSort(arr,begin,keyi - 1,depth,defaultDepth);//depth是当前的深度，defaultDepth是预定的深度。//depth超过dedaultDepth就说明深度有问题IntroSort(arr,keyi + 1,end,depth,defaultDepth);
}void IntroQuickSort(int* a, int left, int right)
{int depth = 0;int logn = 0;int N = right - left + 1;for (int i = 1; i < N; i *= 2){logn++;//计算目标深度}IntroSort(a, left, right, depth, logn * 2);
}

3. 归并排序外排序

3. 1 外排序介绍

外排序（External Sorting）是指能处理极大量数据的排序算法。通常来说，外排序处理的数据不能一次装入内存，只能放在读写较慢的外存储器(通常是硬盘)上。外排序通常采用的是⼀种“排序-归并”的策略。在排序阶段，先读入能放在内存中的数据量，将其排序输出到⼀个临时文件，依此进行，将待排序数据组织为多个有序的临时文件。然后在归并阶段将这些临时文件组合为⼀个大的有序文件，也即排序结果。

3. 2 归并排序外排序的思路

1. 读取n个值排序后写到file1，再读取n个值排序后写到file2。
2. file1和file2利用归并排序的思想，依次读取比较，取小的尾插到mfile，mfile归并为一个有序文件。
3. 将file1和file2删掉，mfile重命名为file1。
4. 再次读取n个数据排序后写到file2。
5. 继续走file1和file2归并，重复步骤2，直到文件中无法读出数据。最后归并出的有序数据放到了file1中。

3. 3 归并排序的实现代码

#include<stdio.h>
#include<time.h>
#include<stdlib.h>void Swap(int* x, int* y)
{int tmp = *x;*x = *y;*y = tmp;
}int compare(const void* a,const void* b)
{return (*(int*)a - *(int*)b);
}int ReadNDataSortToFile(FILE* fout, int n, const char* file1)
{int* a = (int*)malloc(sizeof(int) * n);//创建好一个数组放下抽取出的数据if (a == NULL){perror("malloc error!");return 0;}int x = 0;//创建一个数用来记录抽取出的数据int j = 0;for (int i = 0; i < n; i++){if (fscanf(fout, "%d", &x) == EOF)//从文件中抽取的数据break;//如果x == EOF，说明文件中所有的数均已被抽出，跳出循环a[j++] = x;//j的大小等于已经被抽取的数据}if (a == 0)//如果上面的程序正常运行，而数组a是空的，说明这个文件是空的，已经没有数据了{free(a);//那么就不需要继续抽取文件，直接退出return 0;}qsort(a, j, sizeof(int), compare);//给抽出的数据排好序//打开文件，file1和file2用来存储抽取出的排序好的数据，mfile用来存储归并好的两个文件/*const char* file1 = "file1.txt";const char* file2 = "file2.txt";const char* mfile = "mfile.txt";*/FILE* fin = fopen(file1, "w");//创建一个fin文件，用来放置排好序的数据if (fin == NULL){free(a);perror("fopen error!");return 0;}for (int i = 0; i < j; i++){//阅读文件fprintf(fin, "%d\n", a[i]);//将数据放置进文件中}free(a);//释放数组fclose(fin);//关闭文件return j;//返回的是实际读取到的数据个数。没有数据就返回0。
}void MergeSortFile(const char* file1, const char* file2, const char* mfile)
{//创建好三个临时文件，用来存储排序好的数据FILE* fout1 = fopen(file1, "r");if (fout1 == NULL){perror("fopen1 error!");return 0;}FILE* fout2 = fopen(file2, "r");if (fout2 == NULL){perror("fopen2 error!");return 0;}//但是你要往这个文件中写入，就应该用w的方式打开FILE* mfin = fopen(mfile, "w");//这里用w的方式打开if (mfin == NULL){perror("mfin error!");return 0;}//下面是利用归并排序思路。把比较的数据换成打开文件的形式int x1 = 0, x2 = 0;int ret1 = fscanf(fout1, "%d", &x1);//把fout1的第一个数据赋值给retint ret2 = fscanf(fout2, "%d", &x2);//把fout2的第一个数据赋值给ret//将两个文件的数据进行比较，由小到大依次放进mfile文件中while (ret1 != EOF && ret2 != EOF){if (x1 < x2){fprintf(mfin, "%d\n", x1);ret1 = fscanf(fout1, "%d", &x1);//上一个数据放置完成。赋值下一个数据}else{fprintf(mfin, "%d\n", x2);ret2 = fscanf(fout2, "%d", &x2);}}//上面while跳出的条件，意味着有一个文件的数据没有比较完成。这里对剩余数据进行判断while (ret1 != EOF){fprintf(mfin, "%d\n", x1);ret1 = fscanf(fout1, "%d", &x1);}while (ret2 != EOF){fprintf(mfin, "%d\n", x2);ret2 = fscanf(fout2, "%d", &x2);}//判断完成，需要关闭文件 /*文件使用三部曲1.打开文件2.读取文件3.关闭文件*/fclose(fout1);fclose(fout2);fclose(mfin);
}//创建一个含有随机N个数据的文件
void CreateNData()
{int n = 1000000;srand(time(0));const char* file = "data.txt";FILE* fin = fopen(file,"w");if (fin == NULL){perror("fopen error!");return 0;}for (int i = 0; i < n; i++){int x = rand() + i;fprintf(fin, "%d\n", x);}fclose(fin);
}int main()
{//CreateNData();//创建三个文件，用来排序const char* file1 = "file1.txt";const char* file2 = "file2.txt";const char* mfile = "mfile.txt";//给待排序数组创建一个临时文件FILE* fout = fopen("data.txt", "r");if (fout == NULL){perror("fout fopen error!");return 0;}int m = 100000;//这个是读取要排序的数据，从fout里读取，是读取到这个file1和file2这个文件中，//每个文件读取m个数据ReadNDataSortToFile(fout, m,file1);//这个fout是一个已经打开的文件，怎么能再次打开呢ReadNDataSortToFile(fout, m, file2);//由于data.txt的文件非常大，一次排序不了全部的数据，所以要多次排序while (1)//循环多次排序{//把这个file1和file2中的数据在归并到这个mfile中MergeSortFile(file1, file2, mfile);//删除file1和file2remove(file1);remove(file2);//将mfile重命名为file1rename(mfile, file1);int n = 0;if ((n = ReadNDataSortToFile(fout, m, file2)) == 0)//n=0，说明文件中已经没有数据需要排序了break;}return 0;
}