一.快排
1.快排性能分析
决定快排性能的关键点是每次单趟排序后，key对数组的分割，如果每次选key基本二分居中，那么快排的递归树就是颗均匀的满二叉树，性能最佳。但是实践中虽然不可能每次都是二分居中，但是性能也还是可控的。如果出现每次选到最小值/最大值，划分为0个和N-1的子问题时，时间复杂度为O(N^2)，数组序列有序时就会出现这样的问题，在《八大排序》已经用三数取中或者随机选key解决了这个问题，也就是说我们解决了绝大多数的问题，但是现在还是有一些场景没解决(数组中有大量重复数据时)，类似以下数据。
//数组中有多个跟key相等的值
vector<int> a1 = { 6,1,7,6,6,6,4,9 };
vector<int> a2 = { 3,2,3,3,3,3,2,3 };
//数组中全是相同的值
vector<int> a3 = { 2,2,2,2,2,2,2,2 };
对于以上OJ题，传统的hoare和lomuto(前后指针法)的方法，过不了这个题目。堆排序和归并和希尔是可以过的，其它几个O(N^2)也不过的，因为这个题的测试用例中不仅仅有数据很多的大数组，也有一些特殊数据的数组，如大量重复数据的数组。堆排序和归并和希尔不是很受数据样本的分布和形态的影响，但是快排会，因为快排要选key，每次key都当趟分割都很偏，就会出现效率退化问题。
//hoare版本
class Solution
{
public:
void QuickSort(vector<int>& nums, int left, int right)
{
if(left >= right) return;
int key = nums[left];
int begin = left, end = right;
while(begin < end)
{
while(begin < end && nums[end] >= key) end--;
while(begin < end && nums[begin] <= key) begin++;
swap(nums[begin], nums[end]);
}
swap(nums[left], nums[begin]);
//递归左右区间
//[left, begin - 1] [begin, end] [end + 1, right]
QuickSort(nums, left, begin - 1);
QuickSort(nums, end + 1, right);
}
vector<int> sortArray(vector<int>& nums)
{
QuickSort(nums, 0, nums.size() - 1);
return nums;
}
};
//lomuto版本
class Solution
{
public:
void QuickSort(vector<int>& nums, int left, int right)
{
if(left >= right) return;
int keyi = left;
int prev = left, cur = left + 1;
while(cur <= right)
{
if(nums[cur] < nums[keyi])
{
prev++;
swap(nums[cur], nums[prev]);
}
cur++;
}
swap(nums[prev], nums[keyi]);
keyi = prev;
//递归左右区间
//[left, keyi - 1] keyi [keyi + 1, right]
QuickSort(nums, left, keyi - 1);
QuickSort(nums, keyi + 1, right);
}
vector<int> sortArray(vector<int>& nums)
{
QuickSort(nums, 0, nums.size() - 1);
return nums;
}
};
从上面的的运行结果分析，无论是hoare，还是lomuto的前后指针法，面对key有大量重复时，划分都不是很理想。即使是三数取中和随机选key，都不能很好的解决这里的问题。但是三路划分算法，把跟key相等的值都划分到了中间，可以很好的解决这里的问题。
2.快排之三路划分
三路划分算法解析：当面对有大量跟key相同的值时，三路划分的核心思想有点类似hoare的左右指针和lomuto的前后指针的结合。核心思想是把数组中的数据分为三段【比key小的值】 【与key相等的值】【比key大的值】，所以叫做三路划分算法。结合下图，理解一下实现思想：
- key 默认取 left 位置的值。
- left 指向区间最左边，right 指向区间最后边，cur 指向 left+1 位置。
- cur 遇到比 key 小的值后跟 left 位置交换，换到左边，left++，cur++。
- cur 遇到比 key 大的值后跟 right 位置交换，换到右边，right–。
- cur 遇到跟 key 相等的值后，cur++。
- 直到 cur>right 结束。
class Solution
{
public:
void QuickSort(vector<int>& nums, int left, int right)
{
if(left >= right) return;
//随机选key
int randi = left + (rand() % (right - left + 1)); //注意：加上left
int key = nums[randi];
swap(nums[left], nums[randi]);
//三路划分
int begin = left, end = right, cur = left + 1;
while(cur <= end)
{
if(nums[cur] < key) swap(nums[begin++], nums[cur++]);
else if(nums[cur] > key) swap(nums[cur], nums[end--]);
else cur++;
}
//递归左右区间
//[left, begin - 1] [begin, end] [end + 1, right]
QuickSort(nums, left, begin - 1);
QuickSort(nums, end + 1, right);
}
vector<int> sortArray(vector<int>& nums)
{
QuickSort(nums, 0, nums.size() - 1);
return nums;
}
};
3.快排之内省排序
- C++STL中的sort中用的introspective sort(内省排序)，introsort是由David Musser在1997年设计的排序算法
- introsort是introspective sort采用了缩写，它的实现思路就是进行自我侦测和反省，快排递归深度太深（SGI STL中使用的是深度为2倍排序元素数量的对数值）那就说明在这种数据序列下，选key出现了问题，性能在快速退化，那么就不要再进行快排分割递归了，改换为堆排序进行排序。
introsort的快排：
void Swap(int* x, int* y)
{
int tmp = *x;
*x = *y;
*y = tmp;
}
void AdjustDown(int* a, int n, int parent)
{
int child = parent * 2 + 1;
while (child < n)
{
//选出左右孩子中大的那一个
if (child + 1 < n && a[child + 1] > a[child])
{
++child;
}
if (a[child] > a[parent])
{
Swap(&a[child], &a[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
void HeapSort(int* a, int n)
{
//向下调整建堆：O(N)
for (int i = (n - 1 - 1) / 2; i >= 0; --i)
{
AdjustDown(a, n, i);
}
//排序：O(N*logN)
int end = n - 1;
while (end > 0)
{
Swap(&a[end], &a[0]);
AdjustDown(a, end, 0);
--end;
}
}
void InsertSort(int* a, int n)
{
for (int i = 1; i < n; i++)
{
int end = i - 1;
int tmp = a[i];
//将tmp插入到[0, end]区间中，保持有序
while (end >= 0)
{
if (tmp < a[end])
{
a[end + 1] = a[end];
--end;
}
else
{
break;
}
}
a[end + 1] = tmp;
}
}
void IntroSort(int* a, int left, int right, int depth, int defaultDepth)
{
if (left >= right)
return;
//数组长度小于16的小数组，换为插入排序，简单递归次数
if (right - left + 1 < 16)
{
InsertSort(a + left, right - left + 1);
return;
}
//当深度超过2*logN时改用堆排序
if (depth > defaultDepth)
{
HeapSort(a + left, right - left + 1);
return;
}
depth++;
int begin = left;
int end = right;
//随机选key
int randi = left + (rand() % (right - left));
Swap(&a[left], &a[randi]);
int prev = left;
int cur = prev + 1;
int keyi = left;
while (cur <= right)
{
if (a[cur] < a[keyi] && ++prev != cur)
{
Swap(&a[prev], &a[cur]);
}
++cur;
}
Swap(&a[prev], &a[keyi]);
keyi = prev;
//[begin, keyi-1] keyi [keyi+1, end]
IntroSort(a, begin, keyi - 1, depth, defaultDepth);
IntroSort(a, keyi + 1, end, depth, defaultDepth);
}
void QuickSort(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);
}
int* sortArray(int* nums, int numsSize, int* returnSize)
{
srand(time(0));
QuickSort(nums, 0, numsSize - 1);
*returnSize = numsSize;
return nums;
}
二.归并
1.外排序
- 外排序（External sorting）是指能够处理极大量数据的排序算法。通常来说，外排序处理的数据不能一次装入内存，只能放在读写较慢的外存储器(通常是硬盘)上。外排序通常采用的是一种“排序-归并”的策略。在排序阶段，先读入能放在内存中的数据量，将其排序输出到一个临时文件，依此进行，将待排序数据组织为多个有序的临时文件。然后在归并阶段将这些临时文件组合为一个大的有序文件，也即排序结果。
- 跟外排序对应的就是内排序，我们之前讲的常见的排序，都是内排序，它们排序思想适应的是数据在内存中，支持随机访问。归并排序的思想不需要随机访问数据，只需要依次按序列读取数据，所以归并排序既是一个内排序，也是一个外排序。
2.文件归并排序
- 读取n个值排序后写到file1，再读取n个值排序后写到file2。
- file1和file2利用归并排序的思想，依次读取比较，取小的尾插到mfile，mfile归并为一个有序文件。
- 将file1和file2删掉，mfile重命名为file1。
- 再次读取n个数据排序后写到file2。
- 继续走file1和file2归并，重复步骤2，直到文件中无法读出数据。最后归并出的有序数据放到了file1中。
//创建N个随机数，写到文件中
void CreateNDate()
{
const int n = 10000000;
srand(time(0));
const char* file = "data.txt";
FILE* fin = fopen(file, "w");
if (fin == NULL)
{
perror("fopen error");
return;
}
for (int i = 0; i < n; i++)
{
int x = rand() + i;
fprintf(fin, "%d\n", x);
}
fclose(fin);
}
//qsort用的函数指针
int compare(const void* a, const void* b)
{
return (*(int*)a - *(int*)b);
}
//读取数据后先排序再写到文件中，返回实际读取数据的个数，没有数据则返回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, 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);
}
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 0;
}
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);
//继续读取数据，先排序，再写到file2中：若一个数据都读不到时，说明归并结束，结果在file1中
if (ReadNDataSortToFile(fout, m, file2) == 0)
break;
}
fclose(fout);
return 0;
}