目录
1. 快排性能的关键的分析:
决定快排性能的关键点是每次单躺排序后,key对数组的分割,如果每次选key基本二分居中,那么快排的递归树就是可均匀的满二叉树,性能最佳。但是实践中虽然不可能每次都是二分居中,但是性能也是可控的。但是如果每次选到最小值/最大值,划分成0个和N-1个子问题时,时间复杂度为O(N^2),数组序列有序就会出现这样的问题,我们前面已经使用三数取中或者随机数选key解决了这个问题,也就是说我们解决了绝大多数的问题,但是现在还是有一些场景没解决(数组中有大量重复数据时)。
//数组中有多个和key相等的值
int a1[] = { 6,1,8,6,6,6,6,4,9 };
int a2[] = { 3,2,3,3,3,3,3,2,3 };
//数组中全是相同的值
int a3[] = { 2,2,2,2,2,2,2,2,2 };1.1 三路划分算法思想:
我们之前选key值,比key大的在右边,比key小的在左边,那么和key相等的值并没有规定,也就是说可以在左边也可以在右边,那么三路划分就规定了和key相等的值要放在中间。所谓三路就指的是左边,右边,和中间。
当面对有大量跟key相同的值时,三路划分的核心思想有点类似hoare的左右指针和lomuto的前后指针的结合。核心思想就是把数组中的数据分为3段,比key小的值,跟key相等的值,比key大的值,所有叫做三路划分。
- key默认取left位置的值。
- left指向区间最左边,right指向区间最右边,cur指向left+1位置。
- cur遇到比key小的值后跟left位置交换,换到左边,left++,cur++。
- cur遇到比key大的值后跟right位置交换,换到右边,right--。
- cur遇到跟key相等的值后,cur++。
- 直到cur>right结束。
. - 力扣（LeetCode）. - 备战技术面试？力扣提供海量技术面试资源，帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。
https://leetcode.cn/problems/sort-an-array/这个OJ,当我们用快排的时候,lomuto的方法过不了这个题目,hoare版本可以过这个题目。堆排序和归并和希尔是可以过的,其他几个O(N^2)也过不了,因为这个题的测试用例中部仅仅有数据很大的数组,也有一些特殊数据的数组,如大量重复数据的数组。堆排序和归并排序和希尔不是很受数据样本的分布和形态的影响,但是快排会,因为快排要选key,每次key都当趟分割都很偏,就会出现效率退化问题。
lomuto的前后指针面对大量重复数据时,效率会退化,hoare版本会好很多,所以hoare版本是可以过这个OJ的,但是OJ还是一个相对局限的测试,就像Leetcode官方刚开始写的答案是lomuto,说明那会lomuto是可以过的,后面加了大量重复数据的测试用例,所以就过不了。那么hoare现在可以过,leetcode哪天增加了一个特殊用例以后就过不了,三路划分也类似,因为他们的思想还是在特殊场景下效率会退化,比如大多数选key都是接近最小值或者最大值,导致划分不均衡,效率退化。
- introsort是由David Musser在1997年设计的排序算法,C++ sgi STL sort中用的introspectivesort(内省排序)思想实现的。内省排序可以认为不受数据分布的影响,无论什么原因划分不均匀,导致递归深度太深,它就转换成堆排了,堆排不受数据分布影响。
- 其次三路划分针对有大量重复数据时,效率很好,其他场景就一般,但是三路划分思想还是很有价值的,有些快排思想变形体,要用划分去选数,他能保证跟key相等的数都排到中间去,三路划分的价值就体现出来了。
1.2 三路划分的快排
代码:
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
void Swap(int* x,int* y)
{
int z = *x;
*x = *y;
*y = z;
}
void QuickSort(int* arr,int left,int right)
{
if(left >= right) return;
int begin = left;
int end = right;
//随机数选k,如果数据有序的情况下就保证k不是最小的
int randi = left + (rand() % (right-left + 1));
Swap(&arr[left], &arr[randi]);
int key = arr[left];
int cur = left+1;
while(cur <= right)
{
if(arr[cur] < key)
{
Swap(arr+cur,arr+left);
left++;
cur++;
}
else if(arr[cur] > key)
{
Swap(arr+cur,arr+right);
right--;
}
else cur++;
}
QuickSort(arr,begin,left-1);
QuickSort(arr,right+1,end);
}
int* sortArray(int* nums, int numsSize, int* returnSize) {
srand(time(NULL));
QuickSort(nums,0,numsSize-1);
*returnSize = numsSize;
return nums;
}1.3 introsort的快排
intrsort是introspective sort采用了缩写,他的名字其实表达了他的实现思路,他的思路就是进行自我侦测和反省,快排递归深度太深(sgi stl中使用的是深度为2倍排序元素数量的对数值)那就说明在这种数据序列下,选key出现了问题,性能在快速退化,那么就不要再进行快排分割递归了,改换成堆排序进行排序。
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;
//随机数选k
int randi = left + (rand() % (right-left + 1));
Swap(&a[left], &a[randi]);
int prev = left;
int cur = prev + 1;
int keyi = left;
//lomuto前后指针
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++;
}
// introspective sort -- ⾃省排序
//这里使用2倍的logn的话比较合适,3倍的logn和1倍的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;
}