目录
快速排序的缺陷和解决方法
快速排序的思想就是选出一个key值，一趟排序后让key左边都是小于它的值，key的右边都是大于它的值。然后下一趟排序分别排序key以左的区间，和key以右的区间。
缺陷一：
当整个数组接近有序或者已经有序的情况下，每一次以key值作为分界点，分割递归区间都只能分出一边。
如图：
这样递归的深度就变成了N，时间复杂度就退化成了(1+2+...+N) = （1+N）*N/2。也就是O(N^2)。
为了避免这种情况，有一种解决方法叫做三数取中法：
选出left,mid,right这三个数中的中间值，将它和left交换。
代码实现：
void ThreeNum(int* a, int left, int mid, int right)
{
int max = a[left] > a[mid] ? left : mid;
if (a[right] > a[max])
{
if (a[left] < a[mid])
{
Swap(&a[left], &a[mid]);
}
}
else if (a[right] < a[max])
{
if (a[left] > a[mid])
{
if (a[mid] < a[right])
{
Swap(&a[left], &a[mid]);
}
else {
Swap(&a[left], &a[right]);
}
}
}
}
void QuickSort(int* a, int left, int right)
{
if (left >= right)
return;
//三数取中法让最左边的值是中间值
ThreeNum(a, left, (left + right) / 2, right);
int keyi = PartSort3(a, left, right);//完成一次快排返回keyi的位置
QuickSort(a, left, keyi - 1);
QuickSort(a, keyi + 1, right);
}缺陷二：
另外一个缺陷就是，当递归进行到left和right之间的距离很小的时候（数据量很少并且接近有序）。
空间方面此时任然采用快速排序的方法就会造成很大的栈帧开销（调用函数需要为函数分配栈帧空间）
如图：可以看到，大部分的栈帧开销都是小数据造成的（二叉树最后一层的节点数是所有节点数的一半）
时间方面对于有序的小数据的排序，快速排序的思想并不占优势，快速排序更适合处理数量级比较大的数据。
解决办法：
小区间优化：在数据量较少的情况下，采用插入排序（插入排序对于少量数据的排序适应性很强）。
代码实现：
void QuickSort(int* a, int left, int right)
{
if (left >= right)
return;
//三数取中法让最左边的值是中间值
ThreeNum(a, left, (left + right) / 2, right);
//小区间优化
if ((right - left + 1) < 16)
{
InsertSort(a, (right - left + 1));
}
int keyi = PartSort3(a, left, right);//完成一次快排返回keyi的位置
QuickSort(a, left, keyi - 1);
QuickSort(a, keyi + 1, right);
}缺陷三：
和缺陷一类似，当一组数据中重复数据个数很多的时候，快速排序也会退化成一个O(N^2)的算法。
为了解决这种情况，在进行排序的时候我们选择一种叫做三路划分的算法设计。
所谓三路划分，就是left，cur，right三路。
cur从left+1的位置开始找，当cur处于的位置的值小于key的值时，交换cur和left的值，然后left和cur都+1，当cur所处位置大于key值时，交换cur和right的值，right-1往前找。cur在原地不动，当cur所处的位置的值等于key值时，cur++。一直当cur>right的时候，才结束循环。
这样一趟循环下来，由于left每次++都是和cur交换后。
所以cur遇到了等于key的值之前，left指向的值都是key。
而当cur和left拉开距离后，说明cur遇到了等于key的值。而再次交换left和cur时，会把key的值交换到一串和key相等的值的后面。
而当cur遇到了大于key的值都会停下，一直交换到右边，一直到cur的值是小于或等于key的，cur才会继续往前找。
一趟这样的循环的最终结果就是，left指向了一段相等数的最左边的值，right指向了一段相等数的最右边的值。
这样的然后再递归排序left以左的数据，和right以右的数据，这样的设计方法很好的避免了重复数据过多的时候，快速排序算法时间复杂度退化的情况。
代码实现：
void QuickSort(int* a, int left, int right)
{
if (left >= right)
return;
//三数取中法让最左边的值是中间值
ThreeNum(a, left, (left + right) / 2, right);
//小区间优化
if ((right - left + 1) < 16)
{
InsertSort(a, (right - left + 1));
}
int key = a[left];
int begin = left;
int end = right;
int cur = left + 1;
while (cur <= end)
{
if (a[cur] < key)
{
Swap(&a[cur], &a[begin]);
begin++;
cur++;
}
if (a[cur] > key)
{
Swap(&a[cur], &a[end]);
end--;
}
if (a[cur] == key)
{
cur++;
}
}
QuickSort(a, left, begin);
QuickSort(a, end, right);
}自省排序：
自省排序和以上三种解决办法不一样，它的思想是，不管是什么样的原因导致的快速排序时间复杂度退化，只要检测到函数递归的层次过深，就会切换堆排序。
自省排序在原来的排序基础上，新加了depth和defaultdepth（一般是2*logN）参数，每次进入递归，depth++.
当depth大于defaultdepth时，就切换堆排序，排序剩下的数据。
void QuickSort(int* a, int left, int right,int depth,int defaultdepth)
{
if (left >= right)
return;
//三数取中法让最左边的值是中间值
ThreeNum(a, left, (left + right) / 2, right);
//小区间优化
if ((right - left + 1) < 16)
{
InsertSort(a, (right - left + 1));
}
depth++;
if (depth > defaultdepth)
{
HeapSort(a + left, right - left + 1);
return;
}
int keyi = PartSort3(a, left, right);//完成一次快排返回keyi的位置
QuickSort(a, left, keyi - 1,depth,defaultdepth);
QuickSort(a, keyi + 1, right,depth,defaultdepth);
}文件归并：
归并方法既是内排序，也是外排序，这里的内指的是内存。这是因为我们之前提到的排序算法，都需要随机访问数组的每个位置，而当数据量过大，内存中存不下这些数据时，排序算法就无用武之地了。
而归并排序的算法并不需要随机访问数组的每个位置，它只需要从头到尾遍历两个有序数组。
外存顺序访问的速度远大于随机访问的速度，所以对大型文件排序时，一般都采用归并排序的思路。
采用下面的归并思路比较复杂，由于没法确定每次有多少个小文件会形成，对于不同条件的处理也不一样。
所以我们采用下面的思路：
代码实现：
从源文件中读取n个数据到文件file1中方法：
// 返回实际读到的数据个数，没有数据了，返回0
int ReadNDataSortToFile(FILE* fout, int n, const char* file1)
{
int x = 0;
int* a = (int*)malloc(sizeof(int) * n);
if (a == NULL)
{
perror("malloc error");
return 0;
}
// 想读取n个数据，如果遇到文件结束，应该读到j个
int j = 0;
for (int i = 0; i < n; i++)
{
if (fscanf(fout, "%d", &x) == EOF)
break;
a[j++] = x;
}
if (j == 0)
{
free(a);
return 0;
}
// 排序
qsort(a, j, sizeof(int), compare);
FILE* fin = fopen(file1, "w");
if (fin == NULL)
{
free(a);
perror("fopen error");
return 0;
}
// 写回file1文件
for (int i = 0; i < j; i++)
{
fprintf(fin, "%d\n", a[i]);
}
free(a);
fclose(fin);
return j;
}将两个文件file1和file2归并到第三个文件mfile中的方法：
void MergeFile(const char* file1, const char* file2, const char* mfile)
{
FILE* fout1 = fopen(file1, "r");
if (fout1 == NULL)
{
perror("fopen error");
return;
}
FILE* fout2 = fopen(file2, "r");
if (fout2 == NULL)
{
perror("fopen error");
return;
}
FILE* mfin = fopen(mfile, "w");
if (mfin == NULL)
{
perror("fopen error");
return;
}
// 归并逻辑
int x1 = 0;
int x2 = 0;
int ret1 = fscanf(fout1, "%d", &x1);
int ret2 = fscanf(fout2, "%d", &x2);
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 (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);
}
fclose(fout1);
fclose(fout2);
fclose(mfin);
}
先读取n个数据到file1和file2中，死循环归并，删除file1和file2,将mfile重命名位file1,再入n个数据到file2中，当file2入的数据为0时，结束循环。最后file1中存放的就是排序好的数据。
int main()
{
CreateNDate();
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("fopen error");
return;
}
int m = 1000000;
ReadNDataSortToFile(fout, m, file1);
ReadNDataSortToFile(fout, m, file2);
while (1)
{
MergeFile(file1, file2, mfile);
// 删除file1和file2
remove(file1);
remove(file2);
// 重命名mfile为file1
rename(mfile, file1);
// 当再去读取数据，一个都读不到，说明已经没有数据了
// 已经归并完成，归并结果在file1
int n = 0;
if ((n = ReadNDataSortToFile(fout, m, file2)) == 0)
break;
/*if (n < 100)
{
int x = 0;
}*/
}
return 0;
}