当前位置：首页 > news >正文

快速排序的深入优化探讨

news 来源：原创 2024/9/19 6:56:10

1. 快排性能的关键的分析:

1.1 三路划分算法思想:

1.2 三路划分的快排

1.3 introsort的快排

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;
}