关于快排的细节
2019-08-28

关于快排的主体思想那自然不用说,但是具体代码实现的细节确是很多。下面通过网上找的多个版本来找找其中的细节与优劣。相信只要你对这块不是十分了解或者自己仔细琢磨过细节,那么阅读本文肯定有所收获。

转载请注明,原文来自https://www.cnblogs.com/willhua/p/9426130.html

版本1

public static void quickSort(int[] a, int start, int end) { if (start >= end) return; int t = a[end]; int i = start - 1; for (int j = start; j <= end - 1; j++) { if (a[j] < t) { i++; swap(a, i, j); } } swap(a, i + 1, end); quickSort(a, start, i); quickSort(a, i+2, end); }//来源:https://www.zhihu.com/question/24361443/answer/362777698

分析:这个的特点在于从一头遍历到尾来进行二分,而不像一般的从两头分别开始。对于核心的for循环,首先分析其if,它是当当前处理的元素如果小于t,那么就进行swap,如果大于或者等于t则不会进行交换,这样的话,i就不会增长,也就意味着i表示的是第一个大于或等于t的元素所在的位置,即意味着(i, j)都是属于大于或者等于t的元素。后续处理中,如果if条件满足,那就相当于把第一个大于或者等于t的元素放到当前小于t的位置,同时把这个小于t的元素放到前面的小于t范围的末位,形成了大于或者等于t的范围的翻滚式的向后面移动或者前进的效果。这种写法从语言的简洁上来说是比从两头分别处理的版本的好,但是这种写法会比两头处理的版本更多次的swap,尤其考虑在数组的前面某个范围,其数据本身都是小于t的,那么使用这种版本也会进行很多次swap,即这些swap也根本就没有改变数组的任何排列,或者带来任何变化。

版本2:有bug

void quick_sort(vector<int> &a,int l,int r){ if(l<r) { int po=a[l]; int ll=l,rr=r+1; for(; ;) { while(a[++ll]<po); while(a[--rr]>po); if(ll>rr) break; else swap1(a[ll],a[rr]); } swap1(a[l],a[rr]); quick_sort(a,l,rr); quick_sort(a,rr+1,r); }}//来源:https://www.zhihu.com/question/24361443/answer/362777698

分析:这个版本也是参考的《数据结构与算法分析c++描述》,但改写不成功,有两个明显的bug:

bug1:如果输入的数组a的第一个位置的元素是整个数组的最大值,那么,在while(a[++ll]<po);这句中,因为所有的元素都满足while条件,那么ll必定会执行到数组的最后一位,直至越界报错。bug2:如果输入数组的第一个位置是整个数组的最小值,那么第二个while循环就会出现bug1同样的错误,rr会一直往前走,直至越界报错。

其实,这个bug,在网上很多版本中都存在这样的问题。所以,在《数据结构与算法分析 c语言描述》中特意分析了哨兵设置或者边界处理的细节。

版本3

template <typename T>void quick_sort_recursive(T arr[], int start, int end) { if (start >= end) return; T mid = arr[end]; int left = start, right = end - 1; while (left < right) { while (arr[left] < mid && left < right) left++; //考虑到数组的重复元素,因此这里用的是大于等于号,而不是大于号。 //如果使用大于号,那么当left和 while (arr[right] >= mid && left < right) right--; std::swap(arr[left], arr[right]); } if (arr[left] >= arr[end]) std::swap(arr[left], arr[end]); //left位置为mid else left++; quick_sort_recursive(arr, start, left - 1); quick_sort_recursive(arr, left + 1, end);}template <typename T> //整數或浮點數皆可使用,若要使用物件(class)時必須設定"小於"(<)、"大於"(>)、"不小於"(>=)的運算子功能void quick_sort(T arr[], int len) { quick_sort_recursive(arr, 0, len - 1);}//来源:https://zh.wikipedia.org/wiki/%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F

分析:这个选取的枢纽元是数组的最后一个。这里应该注意的细节有:

在第二个while语句中,增加了left < right的条件。这个就是为了避免产生版本2中的越界bug在第三个while语句中,使用了大于等于号而不是大于,这个细节是为了解决重复元素问题,即当前left和right位置的数据如果都等于mid,那么left++;不会执行,如果下面使用大于的话,那么right--;也不会执行,然后执行玩swap之后,left和right位置的值都还是等于mid,然后重复该步骤,即陷入死循环。但这这种做法的一个弊端是由于左右两边对等于pivot的值的处理方式不相同,容易造成不平衡的分割。由于在第二个和第三个while中,都有left < right条件的限制,那么,当第一个while结束的时候,并不能保证left位置的数值大于等于mid,同样,也不能保证right位置的数值小于mid。所以,在第一个while结束之后,会有一个if-else语句。对于这个if-else,首先可以肯定的是,来到这里之后肯定有left==right。如果是if条件,那么很好理解,执行完之后left位置为mid值,然后分别处理左右两边的。如果是else条件,我们考虑最后一次第一个while循环,记为W。可以肯定的是,在W中,swap的时候已经是left==right了,且要进入到else分之,那么就有left或者right位置的值都小于arr[end],即mid。因此,第二个while停止的条件肯定是left==right(因为arr[left]必须要小于mid)。于是,第三个while也因为left==right停止。即在W中,right的值没有变化,那么说明前一个大循环(假设有,且记为W1)结束时就已经有arr[right]<mid.那么W1结束之后的状态为left<right(因为后面还要执行W循环),且arr[right]<mid。这显然是不能的,因为如果有最终left<right,那么第二个while肯定是因为arr[left]<mid不满足(即arr[left]>=mid)而停止,然后经过swap之后,必定会有arr[right]>=mid.所以W是经历的有且仅有的一次的大while循环。前面已经推出在W中,right值没有变化。那么可以推出,仅仅经过循环W,即在第一次处理第二个while的时候,就已经实现了left==right,于是就可以推出,[left,right]的所有值都小于mid。而mid=arr[end],所以,如果进入了else,在left++;之后,必定有arr[left]==mid=arr[end && left==end成立。于是后面的就都可以理解了。有些会在quick_sort_recursive(arr, start, left - 1);这里加一个if(left)之类的,即避免left-1为复数。这个虽然不加也不会报错,因为到递归调用时,if(start>=end)肯定会满足。但是我认为是有好处的。即通过一次if判断而避免了一次递归调用。但这同时也会给其他情况下的递归多一次if判断。所以,可以考虑把函数最开始的条件判断放到这里来。只要在最初调用的时候进行参数检查即可。

版本4:迭代法

// 参考:http://www.dutor.net/index.php/2011/04/recursive-iterative-quick-sort/struct Range { int start, end; Range(int s = 0, int e = 0) { start = s, end = e; }};template <typename T> // 整數或浮點數皆可使用,若要使用物件(class)時必須設定"小於"(<)、"大於"(>)、"不小於"(>=)的運算子功能void quick_sort(T arr[], const int len) { if (len <= 0) return; // 避免len等於負值時宣告堆疊陣列當機 // r[]模擬堆疊,p為數量,r[p++]為push,r[--p]為pop且取得元素 Range r[len]; int p = 0; r[p++] = Rangelen - 1); while (p) { Range range = r[--p]; if (range.start >= range.end) continue; T mid = arr[range.end]; int left = range.start, right = range.end - 1; while (left < right) { while (arr[left] < mid && left < right) left++; while (arr[right] >= mid && left < right) right--; std::swap(arr[left], arr[right]); } if (arr[left] >= arr[range.end]) std::swap(arr[left], arr[range.end]); else left++; r[p++] = Range(range.start, left - 1); r[p++] = Range(left + 1, range.end); }}//来源:https://zh.wikipedia.org/wiki/%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F

分析

定义了一个处理范围类型Range来表示每次处理的范围通过p值的变化,实现了一个类似的处理流程,即和函数递归的处理流程是一样的设置的的大小,即Range r[len];语句,即为数组的大小。因为当不断迭代之后,每次迭代处理的范围最少为1,所以只需要len就足够了。除非极端情况,比如完全的逆序输入,一般情况不需要len的空间

转载请注明,原文来自https://www.cnblogs.com/willhua/p/9426130.html

版本5:来自《数据结构与算法分析 C语言描述》

#define LEN_LIMINT (3)int median3(int A[], int left, int right){ int mid = (left + right) / 2; if(A[left] > A[mid]) swap(A[left], A[mid]); if(A[left] > A[right]) swap(A[left], A[right]); if(A[mid] > A[right]) swap(A[mid], A[right]); swap(A[mid], A[right-1]); return A[mid];}void quicksort(int a[], int left, int right){ if(left + LEN_LIMINT < right) { int pivot = median3(a, left, right); int ll = left, rr = right - 1; while(ll < rr) { while(a[++ll] < pivot){} while(a[--rr]) > pivot){} if(ll < rr) swap(a[ll], a[rr]); else break; } swap(a[ll], a[right - 1]); quicksort(a, left, ll - 1); quicksort(a, ll + 1, right); } else { //当数组较小的时候,使用插入排序更好 insertionsort(a + left, right - left + 1); }}

分析

使用了median3方法来获取pivot值,并且让a[left]<=a[mid]<=a[right],这样保证了在while中不会发生越界的情况。然后再把pivot放到了right-1的位置,这也会对ll起到警戒作用由于上面提到的警戒作用的存在,因此不用像版本3一样,还判断left<right由于在median3中就已经对left,mid,right排序,所以在while中可以使用前置符号,一开始就把ll和rr分别初始化为left+1和right-2对于while循环,如果使用while(a[ll]<pivot) ll++;while(a[rr]>pivot) rr--;来替代,那么可能出现ll和rr位置都等于pivot的,那么就会死循环的情况。对于LEN_LIMIT,从快排与插入排序的性质考虑,推荐的值是10。这样比完全使用快排大概快15%。5到20之间都算合适。如果小于3,那么median3取三个值,却实际上只取了一个或者两个值,在细节上可能更加麻烦。

枢纽元pivot选择

选择第一个元素:如果输入是随机的,那么这种做法是可以接受,如果输入是预排序的,那么这种做法就是不可接受的。因为这样会导致劣质的分割,分割的两边极度不均衡,甚至分割相当于啥也没干。在实际情况中,大部分时候都是预排序的,因此,这种做法应当放弃。还有一种类似的想法就是取两个互异的关键字中大者,这种做法有同样的坏处。随机选取枢纽:这种做法是安全的,但是问题在随机的开销都是昂贵的。三数中值分割法:最理想的枢纽值应该是当前数组的中值,但是为了获得这个中值都需要进行排序,开销很大。所以,可以考虑随机取数组中的三个值,把其中的中值作为枢纽元。但是,实际上,随机选取并没有太大的明显意义,所以一般取数组的头尾和中间位置的三个值,然后取其中值作为枢纽元,根据统计,这种做法大约会提升5%的速度,也是最为推荐的做法