「数组」快速排序 / 随机值优化|小区间插入优化（C++） ...

概述

在上一篇文章中，我们介绍了三种基本的暴力排序：
「数组」冒泡排序|选择排序|插入排序 / 及优化方案（C++）
他们的时间复杂度均为O(n²)级别。
在这篇文章，我们将介绍其中的第一个算法：冒泡排序的究极promax进化版：快速排序。
经过重重优化的冒泡排序几乎是最快的排序算法，可谓是从冒泡这个几乎最慢的排序彻底脱胎换骨。
思路

   我们先追念一下冒泡排序的算法过程：
  在第i轮循环他总把第i大的数放在数组末尾。这带来的影响是什么？
  那就是它的下一次循环的遍历范围比这次循环范围只小了1个数而已。
  那如果我们不在第i轮循环找第i大的数会发生什么？
  在一个大小为n的无序数组中， 
假设我们在第一次循环能够把第k小中位数（大概一个很靠近中间的数）放在位置k上，也就是它在排好后的有序数组里所处的位置。
我们发现：只需要分别对它的左侧和右侧举行遍历就可以了，而这两次遍历的范围都至于都缩小到了n/2。
而他们又分别能使得第i小的数放在位置i上，第j小的数放在位置j上（0<=i<k<j<=n-1）。
我们发现：将这三个数（i,j,k）在乱序数组中排好序（即放在数组彻底有序时他们所应该在的位置），前三次遍历的范围是：n+n/2+n/2=2n。
而冒泡的前三次遍历的范围是： n+n-1+n-2=3n-3。
在n极其巨大，这个提升是极其显著的，并且，对于k所分别出的左右两个小区间，这两个小区间的首次遍历所分别出的小小区间也有这样的性子，一直可以递推到区间长度为1，它们都有这样的性子。
这就是分治。
算法过程

   这个过程往往依赖递归实现。
  quick_sort()

我们给出函数quick_sort，它接收一个范围，它只干两件事：
①将这个范围中的一个数放在它应该在的位置 
②这个数分别出的左右两个小范围传入quick_sort
*注意* :如果你首次接触递归，那么你应该认识到上一级quick_sort和下一级quick_sort并不是同一个函数，他们只是有相同的名字，执行相同的功能。
一直到小范围长度减少到1为止（1个数天生有序）。
在这里，我们用partition函数执行这个分区操作。

1. void quick_sort(int arr[], int l,int r) {
2.         if (r-l<=1)return ;
3.         int pos = partition(arr, l, r);
4.         quick_sort(arr, l, pos);
5.         quick_sort(arr, pos + 1, r);
6. }

复制代码

pos表现分区完成后某个已安放好的数所处的位置。 
 *注意*：根据代码语言传统，l和r往往是一个左闭右开区间，即[l,r），表现范围取到l，但取不到r。

---

partition()

 我们给出函数partition()，它接收一个范围，它只干一件事：
在区间里找个数，给它安放好，然后返回安放位置。
一般我们把这个数称为pivot（基准数）。 
朴素的快速排序直接选择第一个数当基准数。
我们这样明白安放基准数：那无非就是把比他大的数放在它右边，比它小的数放在它左边，只有左边范围和右边范围的内部是否有序，我不关心。
以同向双指针游走实现这件事：
先把要安放的基准数放在数组末尾，防止它干扰我们分别。（现在数组末尾就是基准数）
i和j一开始都指向范围内的第一个数：
①如果第一个数大于基准数，j进步，i不动，随后j发现的所有大于基准数的数，如此直到j发现了小于即是基准数的数：那就互换j指向的数和i指向的数，然后i进步一位，j继续往前走。
②如果第一个数小于即是基准数，那么i和j齐头并进继续走（在代码层面上其实这里一直在发生本身与本身互换），直到i和j指向的数比基准数大，j与i发生分离，i留下来维护这个数，j继续向前探索。
这样明白：
在一轮循环后，
i总是指向第一个大于基准数的数，i身后的数都小于即是基准数；
j总是指向未知区域的第一个数，j身后一直到i的范围是已经探明的比基准数大的数。

1. 某次循环结束后（p为基准数位置）
2.   
3.               |
4.             | |     |
5.             | | | | | |
6.     |     | | | | | | |   |   |
7.     | |   | | | | | | |   |   |
8.   | | | | | | | | | | | | | | |
9. ------------------------------------
10.   l         i           j     p  r
12. *注意*：位置r不在这个区间范围内，p才是最后一个位置。

复制代码

1. int partition(int arr[], int l, int r) {
2.         swap(arr[l], arr[r-1]);
3.         int i, j;
4.         for (i = l, j = l; j <= r - 1; j++)
5.                 if (arr[j] <= arr[r - 1])swap(arr[i++], arr[j]);
6.         return i-1;
7. }

复制代码

 在j抵达基准数后，基准数被向前互换到了它需要被安放的位置。
注意此时由于i++，我们返回i-1。

---

Code

1. int partition(int arr[], int l, int r) {
2.         swap(arr[l], arr[r-1]);
3.         int i, j;
4.         for (i = l, j = l; j <= r - 1; j++)
5.                 if (arr[j] <= arr[r - 1])swap(arr[i++], arr[j]);
6.         return i-1;
7. }void quick_sort(int arr[], int l,int r) {
8.         if (r-l<=1)return ;
9.         int pos = partition(arr, l, r);
10.         quick_sort(arr, l, pos);
11.         quick_sort(arr, pos + 1, r);
12. }

复制代码

优化方案

随机数优化

还记得快速排序是冒泡排序的究极promax进化版吗？它但是会退化的。
如果你选择的基准数总是区间最左侧的数，而整个数组本身相称有序，那么你的分别得到的左侧和右侧范围长度就是1和n-1。如此一来快排就退化回了冒泡。。
处理惩罚方法也很简单：在范围里随机取个数当基准数，而不是固定取最左边，这样就实现了随机分区函数。
关于C++标准库中的random文件的简单应用可参考：「数组」Knuth洗牌算法|C++random库简单介绍 / LeetCode 384（C++）

1. mt19937 mt;
2. int random_partition(int arr[], int l, int r) {
3.         int pos = mt() % (r - l) + l;
4.         swap(arr[pos], arr[r - 1]);
5.         int i, j;
6.         for (i = l, j = l; j <= r - 1; j++)
7.                 if (arr[j] <= arr[r - 1])swap(arr[i++], arr[j]);
8.         return i - 1;
9. }

复制代码

小区间插入优化

最底层的quick_sort会调用大量的分区函数，而他们分区的范围却极小，这是不必要的，而且会相称被动地占用大量空间（函数的调用会占用空间资源）。
插入排序在小区间的表现要好于快速分区，当分区小到某个程度时，我们直接转发给插入排序。

1. void QKsort(int arr[], int l, int r) {
2.         if (r - l <= 20) {
3.                 insertion_sort(&arr[l],r-l);
4.                 return;
5.         }
6.         int pos = random_partition(arr, l, r);
7.         QKsort(arr, l, pos);
8.         QKsort(arr, pos + 1, r);
9. }

复制代码

Code(pro)

1. mt19937 mt;
2. int random_partition(int arr[], int l, int r) {
3.         int pos = mt() % (r - l) + l;
4.         swap(arr[pos], arr[r - 1]);
5.         int i, j;
6.         for (i = l, j = l; j <= r - 1; j++)
7.                 if (arr[j] <= arr[r - 1])swap(arr[i++], arr[j]);
8.         return i - 1;
9. }void QKsort(int arr[], int l, int r) {
10.         if (r - l <= 20) {
11.                 insertion_sort(&arr[l],r-l);
12.                 return;
13.         }
14.         int pos = random_partition(arr, l, r);
15.         QKsort(arr, l, pos);
16.         QKsort(arr, pos + 1, r);
17. }

复制代码

复杂度

   时间复杂度：O(nlogn)
  空间复杂度：O(logn)
  复杂度分析：
时间分析：
 在理想情况下，每次都正好实现了区域均分。
设总用时为T(n)，那么
T(n)=T(n/2)+T(n/2)+n。···①
（n为本次分区所用时间，两个T(n/2)为下一级的总时间）
注意到，
T(n/2)=T(n/4)+T(n/4)+n/2。···②，代入①得到：
T(n)=T(n/4)+T(n/4)+n/2+T(n/4)+T(n/4)+n/2+n
       =4T(n/4)+2n
如此迭代得到：T(n)=2^mT(1)+mn
（m为迭代折半从n得到1的次数，即m=logn）
即T(n)=nT(1)+nlogn=n+nlogn，省去小量，得到O(nlogn)。

---

空间分析： 
在分割数组时，观察：

1. --------------------------------------
2. ----------------- --------------------
3. --------- ------- ------ -------------
4. --- ----- --- --  -- --- --- ---------
5. - - - --- - - --  -- - - - - ---- ----
6. - - - - - - - - - - - - - - - - - - --
7. 共有logn层

复制代码

*注意*：同一层的每次小函数结束后空间会被开释，下次函数都会再次占据这块空间
空间复用使得每一层的复杂度都是O(1)，整体为O(logn) 。
因此空间复杂度是logn级别的。
百万数目级抗压测试

1. int main()
2. {   int nums = 5000000;
3.         int* arr1 = new int[nums];
4.         int* arr2 = new int[nums];
5.         for (int i = 0; i < nums; i++) {
6.                 int x = mt();
7.                 arr1[i] = x;
8.                 arr2[i] = x;
9.         }
11.         DWORD tick1 = GetTickCount64();
12.         quick_sort(arr1, 0,nums);//show(arr1, nums);
13.         DWORD tick2 = GetTickCount64();
14.         cout << "原始快速排序(霍尔法)(ms):" << tick2 - tick1 << endl;
15.                
16.         DWORD tick3 = GetTickCount64();
17.         QKsort(arr2, 0, nums); //show(arr2, nums);
18.         DWORD tick4 = GetTickCount64();
19.         cout << "随机并转发小区间优化(ms):" << tick4 - tick3 << endl;
21.         delete[]arr1;
22.         delete[]arr2;
23.         return 0;
24. }

复制代码

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