【数据布局】快排之三路划分+文件归并排序

一.快排

1.快排性能分析

决定快排性能的关键点是每次单趟排序后，key对数组的分割，假如每次选key基本二分居中，那么快排的递归树就是颗均匀的满二叉树，性能最佳。但是实践中固然不大概每次都是二分居中，但是性能也还是可控的。假如出现每次选到最小值/最大值，划分为0个和N-1的子问题时，时间复杂度为O(N^2)，数组序列有序时就会出现如许的问题，在《八大排序》已经用三数取中或者随机选key解决了这个问题，也就是说我们解决了绝大多数的问题，但是现在还是有一些场景没解决(数组中有大量重复数据时)，类似以下数据。

1. //数组中有多个跟key相等的值
2. vector<int> a1 = { 6,1,7,6,6,6,4,9 };
3. vector<int> a2 = { 3,2,3,3,3,3,2,3 };
5. //数组中全是相同的值
6. vector<int> a3 = { 2,2,2,2,2,2,2,2 };

复制代码

leetcode：排序数组
对于以上OJ题，传统的hoare和lomuto(前后指针法)的方法，过不了这个标题。堆排序和归并和希尔是可以过的，其它几个O(N^2)也不过的，由于这个题的测试用例中不仅仅有数据很多的大数组，也有一些特殊数据的数组，如大量重复数据的数组。堆排序和归并和希尔不是很受数据样本的分布和形态的影响，但是快排会，由于快排要选key，每次key都当趟分割都很偏，就会出现效率退化问题。

1. //hoare版本
2. class Solution
3. {
4. public:
5.     void QuickSort(vector<int>& nums, int left, int right)
6.     {
7.         if(left >= right) return;
9.         int key = nums[left];
10.         int begin = left, end = right;
12.         while(begin < end)
13.         {
14.             while(begin < end && nums[end] >= key) end--;
15.             while(begin < end && nums[begin] <= key) begin++;
16.             swap(nums[begin], nums[end]);
17.         }
18.         swap(nums[left], nums[begin]);
20.         //递归左右区间
21.         //[left, begin - 1] [begin, end] [end + 1, right]
22.         QuickSort(nums, left, begin - 1);
23.         QuickSort(nums, end + 1, right);
24.     }
26.     vector<int> sortArray(vector<int>& nums)
27.     {
28.         QuickSort(nums, 0, nums.size() - 1);
29.         return nums;
30.     }
31. };

复制代码

1. //lomuto版本
2. class Solution
3. {
4. public:
5.     void QuickSort(vector<int>& nums, int left, int right)
6.     {
7.         if(left >= right) return;
9.             int keyi = left;
10.             int prev = left, cur = left + 1;
11.             while(cur <= right)
12.             {
13.                     if(nums[cur] < nums[keyi])
14.                     {
15.                             prev++;
16.                             swap(nums[cur], nums[prev]);
17.                     }
18.                     cur++;
19.             }
20.             swap(nums[prev], nums[keyi]);
21.             keyi = prev;
23.             //递归左右区间
24.             //[left, keyi - 1] keyi [keyi + 1, right]
25.             QuickSort(nums, left, keyi - 1);
26.             QuickSort(nums, keyi + 1, right);
27.     }
29.     vector<int> sortArray(vector<int>& nums)
30.     {
31.         QuickSort(nums, 0, nums.size() - 1);
32.         return nums;
33.     }
34. };

复制代码

从上面的的运行结果分析，无论是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 结束。
  

1. class Solution
2. {
3. public:
4.     void QuickSort(vector<int>& nums, int left, int right)
5.     {
6.         if(left >= right) return;
8.         //随机选key
9.         int randi = left + (rand() % (right - left + 1)); //注意：加上left
10.         int key = nums[randi];
11.         swap(nums[left], nums[randi]);
13.         //三路划分
14.         int begin = left, end = right, cur = left + 1;
15.         while(cur <= end)
16.         {
17.             if(nums[cur] < key) swap(nums[begin++], nums[cur++]);
18.             else if(nums[cur] > key) swap(nums[cur], nums[end--]);
19.             else cur++;
20.         }
22.         //递归左右区间
23.         //[left, begin - 1] [begin, end] [end + 1, right]
24.         QuickSort(nums, left, begin - 1);
25.         QuickSort(nums, end + 1, right);
26.     }
28.     vector<int> sortArray(vector<int>& nums)
29.     {
30.         QuickSort(nums, 0, nums.size() - 1);
31.         return nums;
32.     }
33. };

复制代码

3.快排之内省排序

• C++STL中的sort中用的introspective sort(内省排序)，introsort是由David Musser在1997年设计的排序算法
  
• introsort是introspective sort采用了缩写，它的实现思路就是进行自我侦测和反省，快排递归深度太深（SGI STL中使用的是深度为2倍排序元素数目的对数值）那就说明在这种数据序列下，选key出现了问题，性能在快速退化，那么就不要再进行快排分割递归了，改换为堆排序进行排序。
  

introsort的快排：

1. void Swap(int* x, int* y)
2. {
3.         int tmp = *x;
4.         *x = *y;
5.         *y = tmp;
6. }
8. void AdjustDown(int* a, int n, int parent)
9. {
10.         int child = parent * 2 + 1;
11.         while (child < n)
12.         {
13.                 //选出左右孩子中大的那一个
14.                 if (child + 1 < n && a[child + 1] > a[child])
15.                 {
16.                         ++child;
17.                 }
18.                 if (a[child] > a[parent])
19.                 {
20.                         Swap(&a[child], &a[parent]);
21.                         parent = child;
22.                         child = parent * 2 + 1;
23.                 }
24.                 else
25.                 {
26.                         break;
27.                 }
28.         }
29. }
31. void HeapSort(int* a, int n)
32. {
33.         //向下调整建堆：O(N)
34.         for (int i = (n - 1 - 1) / 2; i >= 0; --i)
35.         {
36.                 AdjustDown(a, n, i);
37.         }
39.         //排序：O(N*logN)
40.         int end = n - 1;
41.         while (end > 0)
42.         {
43.                 Swap(&a[end], &a[0]);
44.                 AdjustDown(a, end, 0);
45.                 --end;
46.         }
47. }
49. void InsertSort(int* a, int n)
50. {
51.         for (int i = 1; i < n; i++)
52.         {
53.                 int end = i - 1;
54.                 int tmp = a[i];
55.                 //将tmp插入到[0, end]区间中，保持有序
56.                 while (end >= 0)
57.                 {
58.                         if (tmp < a[end])
59.                         {
60.                                 a[end + 1] = a[end];
61.                                 --end;
62.                         }
63.                         else
64.                         {
65.                                 break;
66.                         }
67.                 }
68.                 a[end + 1] = tmp;
69.         }
70. }
72. void IntroSort(int* a, int left, int right, int depth, int defaultDepth)
73. {
74.         if (left >= right)
75.                 return;
77.         //数组长度小于16的小数组，换为插入排序，简单递归次数
78.         if (right - left + 1 < 16)
79.         {
80.                 InsertSort(a + left, right - left + 1);
81.                 return;
82.         }
84.         //当深度超过2*logN时改用堆排序
85.         if (depth > defaultDepth)
86.         {
87.                 HeapSort(a + left, right - left + 1);
88.                 return;
89.         }
90.         depth++;
91.         int begin = left;
92.         int end = right;
94.         //随机选key
95.         int randi = left + (rand() % (right - left));
96.         Swap(&a[left], &a[randi]);
97.         int prev = left;
98.         int cur = prev + 1;
99.         int keyi = left;
100.         while (cur <= right)
101.         {
102.                 if (a[cur] < a[keyi] && ++prev != cur)
103.                 {
104.                         Swap(&a[prev], &a[cur]);
105.                 }
106.                 ++cur;
107.         }
108.         Swap(&a[prev], &a[keyi]);
109.         keyi = prev;
111.         //[begin, keyi-1] keyi [keyi+1, end]
112.         IntroSort(a, begin, keyi - 1, depth, defaultDepth);
113.         IntroSort(a, keyi + 1, end, depth, defaultDepth);
114. }
116. void QuickSort(int* a, int left, int right)
117. {
118.         int depth = 0;
119.         int logn = 0;
120.         int N = right - left + 1;
121.         for (int i = 1; i < N; i *= 2)
122.         {
123.                 logn++;
124.         }
126.         //自省排序
127.         IntroSort(a, left, right, depth, logn * 2);
128. }
130. int* sortArray(int* nums, int numsSize, int* returnSize)
131. {
132.         srand(time(0));
133.         QuickSort(nums, 0, numsSize - 1);
134.         *returnSize = numsSize;
135.        
136.         return nums;
137. }

复制代码

二.归并

1.外排序

• 外排序（External sorting）是指能够处理极大量数据的排序算法。通常来说，外排序处理的数据不能一次装入内存，只能放在读写较慢的外存储器(通常是硬盘)上。外排序通常采用的是一种“排序-归并”的策略。在排序阶段，先读入能放在内存中的数据量，将其排序输出到一个临时文件，依此进行，将待排序数据构造为多个有序的临时文件。然后在归并阶段将这些临时文件组合为一个大的有序文件，也即排序结果。
  
• 跟外排序对应的就是内排序，我们之前讲的常见的排序，都是内排序，它们排序思想顺应的是数据在内存中，支持随机访问。归并排序的思想不需要随机访问数据，只需要依次按序列读取数据，所以归并排序既是一个内排序，也是一个外排序。
  

2.文件归并排序

• 读取n个值排序后写到file1，再读取n个值排序后写到file2。
  
• file1和file2使用归并排序的思想，依次读取比较，取小的尾插到mfile，mfile归并为一个有序文件。
  
• 将file1和file2删掉，mfile重定名为file1。
  
• 再次读取n个数据排序后写到file2。
  
• 继承走file1和file2归并，重复步调2，直到文件中无法读出数据。最后归并出的有序数据放到了file1中。
  

1. //创建N个随机数，写到文件中
2. void CreateNDate()
3. {
4.         const int n = 10000000;
5.         srand(time(0));
6.         const char* file = "data.txt";
7.         FILE* fin = fopen(file, "w");
8.         if (fin == NULL)
9.         {
10.                 perror("fopen error");
11.                 return;
12.         }
14.         for (int i = 0; i < n; i++)
15.         {
16.                 int x = rand() + i;
17.                 fprintf(fin, "%d\n", x);
18.         }
20.         fclose(fin);
21. }
23. //qsort用的函数指针
24. int compare(const void* a, const void* b)
25. {
26.         return (*(int*)a - *(int*)b);
27. }
29. //读取数据后先排序再写到文件中，返回实际读取数据的个数，没有数据则返回0
30. int ReadNDataSortToFile(FILE* fout, int n, const char* file1)
31. {
32.         //开辟数组
33.         int x = 0;
34.         int* a = (int*)malloc(sizeof(int) * n);
35.         if (a == NULL)
36.         {
37.                 perror("malloc error");
38.                 return 0;
39.         }
41.         //读取N个数据到数组中，如果遇到文件结束，实际读到j个
42.         int j = 0;
43.         for (int i = 0; i < n; i++)
44.         {
45.                 if (fscanf(fout, "%d", &x) == EOF)
46.                         break;
48.                 a[j++] = x;
49.         }
51.         if (j == 0)
52.         {
53.                 free(a);
54.                 return 0;
55.         }
57.         //内排序
58.         qsort(a, j, sizeof(int), compare);
60.         //创建文件
61.         FILE* fin = fopen(file1, "w");
62.         if (fin == NULL)
63.         {
64.                 free(a);
65.                 perror("fopen error");
66.                 return 0;
67.         }
69.         //写排序后的数据到file1文件中
70.         for (int i = 0; i < j; i++)
71.         {
72.                 fprintf(fin, "%d\n", a[i]);
73.         }
75.         free(a);
76.         fclose(fin);
78.         return j;
79. }
81. //将file1与file2中的数据归并到mfile文件中
82. void MergeFile(const char* file1, const char* file2, const char* mfile)
83. {
84.         FILE* fout1 = fopen(file1, "r");
85.         if (fout1 == NULL)
86.         {
87.                 perror("fopen error");
88.                 return;
89.         }
91.         FILE* fout2 = fopen(file2, "r");
92.         if (fout2 == NULL)
93.         {
94.                 perror("fopen error");
95.                 return;
96.         }
98.         FILE* mfin = fopen(mfile, "w");
99.         if (mfin == NULL)
100.         {
101.                 perror("fopen error");
102.                 return;
103.         }
105.         int x1 = 0, x2 = 0;
106.         int ret1 = fscanf(fout1, "%d", &x1);
107.         int ret2 = fscanf(fout2, "%d", &x2);
109.         while (ret1 != EOF && ret2 != EOF)
110.         {
111.                 if (x1 < x2)
112.                 {
113.                         fprintf(mfin, "%d\n", x1);
114.                         ret1 = fscanf(fout1, "%d", &x1);
115.                 }
116.                 else
117.                 {
118.                         fprintf(mfin, "%d\n", x2);
119.                         ret2 = fscanf(fout2, "%d", &x2);
120.                 }
121.         }
122.         while (ret1 != EOF)
123.         {
124.                 fprintf(mfin, "%d\n", x1);
125.                 ret1 = fscanf(fout1, "%d", &x1);
126.         }
127.         while (ret2 != EOF)
128.         {
129.                 fprintf(mfin, "%d\n", x2);
130.                 ret2 = fscanf(fout2, "%d", &x2);
131.         }
133.         fclose(fout1);
134.         fclose(fout2);
135.         fclose(mfin);
136. }
138. int main()
139. {
140.         CreateNDate();
142.         const char* file1 = "file1.txt";
143.         const char* file2 = "file2.txt";
144.         const char* mfile = "mfile.txt";
146.         FILE* fout = fopen("data.txt", "r");
147.         if (fout == NULL)
148.         {
149.                 perror("fopen error");
150.                 return 0;
151.         }
153.         int m = 1000000;
154.         ReadNDataSortToFile(fout, m, file1);
155.         ReadNDataSortToFile(fout, m, file2);
157.         while (1)
158.         {
159.                 MergeFile(file1, file2, mfile);
161.                 //删除file1和file2
162.                 remove(file1);
163.                 remove(file2);
165.                 //将mfile重命名为file1
166.                 rename(mfile, file1);
168.                 //继续读取数据，先排序，再写到file2中：若一个数据都读不到时，说明归并结束，结果在file1中
169.                 if (ReadNDataSortToFile(fout, m, file2) == 0)
170.                         break;
171.         }
173.         fclose(fout);
175.         return 0;
176. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。