文章目录
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进行划分。直到全部划分完成。
具体的实现思路：
key默认取left位置的值。
left指向区间最左边，right指向区间最后边，cur指向left+1位置。
cur遇到比key小的值后跟left位置交换，换到左边，left++，cur++。
例如上面的数组，由于1 < 6，所以1换到6的位置上。
一直重复，直到 left 交换完。得到：
- cur遇到比key大的值后跟right位置交换，换到右边，right-- 。
接着以上述数组举例。左边数组交换完成，接着交换右边数组：
重复交换，得到：
cur遇到跟key相等的值后，cur++。
直到cur > right结束
最终得到：
这样就将数组分成了三个区域。
1. 3 代码实现
//三路划分
void ThreeWaySort(int* arr, int left, int right)
{
if (left >= right)
{
return;
}
//取一个随机值当key
int 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]);//随机数取key
int 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 归并排序外排序的思路
- 读取n个值排序后写到file1，再读取n个值排序后写到file2。
- file1和file2利用归并排序的思想，依次读取比较，取小的尾插到mfile，mfile归并为一个有序文件。
- 将file1和file2删掉，mfile重命名为file1。
- 再次读取n个数据排序后写到file2。
- 继续走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的第一个数据赋值给ret
int 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和file2
remove(file1);
remove(file2);
//将mfile重命名为file1
rename(mfile, file1);
int n = 0;
if ((n = ReadNDataSortToFile(fout, m, file2)) == 0)//n=0，说明文件中已经没有数据需要排序了
break;
}
return 0;
}