「数组」快速排序 / 随机值优化|小区间插入优化（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函数执行这个分区操作。
void quick_sort(int arr[], int l,int r) {
if (r-l<=1)return ;
int pos = partition(arr, l, r);
quick_sort(arr, l, pos);
quick_sort(arr, pos + 1, r);
} pos表现分区完成后某个已安放好的数所处的位置。
*注意*：根据代码语言传统，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的范围是已经探明的比基准数大的数。
某次循环结束后（p为基准数位置）
|
| | |
| | | | | |
| | | | | | | | | |
| | | | | | | | | | |
| | | | | | | | | | | | | | |
------------------------------------
l i j pr
*注意*：位置r不在这个区间范围内，p才是最后一个位置。 int partition(int arr[], int l, int r) {
swap(arr, arr);
int i, j;
for (i = l, j = l; j <= r - 1; j++)
if (arr <= arr)swap(arr, arr);
return i-1;
} 在j抵达基准数后，基准数被向前互换到了它需要被安放的位置。
注意此时由于i++，我们返回i-1。
Code
int partition(int arr[], int l, int r) {
swap(arr, arr);
int i, j;
for (i = l, j = l; j <= r - 1; j++)
if (arr <= arr)swap(arr, arr);
return i-1;
}void quick_sort(int arr[], int l,int r) {
if (r-l<=1)return ;
int pos = partition(arr, l, r);
quick_sort(arr, l, pos);
quick_sort(arr, pos + 1, r);
} 优化方案
随机数优化
还记得快速排序是冒泡排序的究极promax进化版吗？它但是会退化的。
如果你选择的基准数总是区间最左侧的数，而整个数组本身相称有序，那么你的分别得到的左侧和右侧范围长度就是1和n-1。如此一来快排就退化回了冒泡。。
处理惩罚方法也很简单：在范围里随机取个数当基准数，而不是固定取最左边，这样就实现了随机分区函数。
关于C++标准库中的random文件的简单应用可参考：「数组」Knuth洗牌算法|C++random库简单介绍 / LeetCode 384（C++）
mt19937 mt;
int random_partition(int arr[], int l, int r) {
int pos = mt() % (r - l) + l;
swap(arr, arr);
int i, j;
for (i = l, j = l; j <= r - 1; j++)
if (arr <= arr)swap(arr, arr);
return i - 1;
} 小区间插入优化
最底层的quick_sort会调用大量的分区函数，而他们分区的范围却极小，这是不必要的，而且会相称被动地占用大量空间（函数的调用会占用空间资源）。
插入排序在小区间的表现要好于快速分区，当分区小到某个程度时，我们直接转发给插入排序。
void QKsort(int arr[], int l, int r) {
if (r - l <= 20) {
insertion_sort(&arr,r-l);
return;
}
int pos = random_partition(arr, l, r);
QKsort(arr, l, pos);
QKsort(arr, pos + 1, r);
} Code(pro)
mt19937 mt;
int random_partition(int arr[], int l, int r) {
int pos = mt() % (r - l) + l;
swap(arr, arr);
int i, j;
for (i = l, j = l; j <= r - 1; j++)
if (arr <= arr)swap(arr, arr);
return i - 1;
}void QKsort(int arr[], int l, int r) {
if (r - l <= 20) {
insertion_sort(&arr,r-l);
return;
}
int pos = random_partition(arr, l, r);
QKsort(arr, l, pos);
QKsort(arr, pos + 1, r);
} 复杂度
时间复杂度：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)。
空间分析：
在分割数组时，观察：
--------------------------------------
----------------- --------------------
--------- ------- ------ -------------
--- ----- --- ---- --- --- ---------
- - - --- - - ---- - - - - ---- ----
- - - - - - - - - - - - - - - - - - --
共有logn层 *注意*：同一层的每次小函数结束后空间会被开释，下次函数都会再次占据这块空间
空间复用使得每一层的复杂度都是O(1)，整体为O(logn) 。
因此空间复杂度是logn级别的。
百万数目级抗压测试
int main()
{ int nums = 5000000;
int* arr1 = new int;
int* arr2 = new int;
for (int i = 0; i < nums; i++) {
int x = mt();
arr1 = x;
arr2 = x;
}
DWORD tick1 = GetTickCount64();
quick_sort(arr1, 0,nums);//show(arr1, nums);
DWORD tick2 = GetTickCount64();
cout << "原始快速排序(霍尔法)(ms):" << tick2 - tick1 << endl;
DWORD tick3 = GetTickCount64();
QKsort(arr2, 0, nums); //show(arr2, nums);
DWORD tick4 = GetTickCount64();
cout << "随机并转发小区间优化(ms):" << tick4 - tick3 << endl;
delete[]arr1;
delete[]arr2;
return 0;
} https://i-blog.csdnimg.cn/direct/be8a5c7cf54348eba16d72993efc8154.png
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]