快速排序-族谱新闻-族谱网

快速排序

2020-10-16

出处：族谱网

作者：阿族小谱

浏览:595次

转发:0次

评论:0

算法快速排序采用“分而治之、各个击破”的观念，此为原地（In-place）分区版本。快速排序使用分治法（Divideandconquer）策略来把一个序列（list）分为两个子序列（sub-lists）。步骤为：从数列中挑出一个元素，称为"基准"（pivot），重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（相同的数可以到任一边）。在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。递归地（recursively）把小于基准值元素的子数列和大于基准值元素的子数列排序。递归到最底部时，数列的大小是零或一，也就是已经排序好了。这个算法一定会结束，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。在简单的伪代码中，此算法可以被表示为：原地（in-place）分区的版本上面简单版本的缺点是，它需要...

算法

快速排序采用“分而治之、各个击破”的观念，此为原地（In-place）分区版本。

快速排序使用分治法（Divide and conquer）策略来把一个序列（list）分为两个子序列（sub-lists）。

步骤为：

从数列中挑出一个元素，称为"基准"（pivot），

重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（相同的数可以到任一边）。在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。

递归地（recursively）把小于基准值元素的子数列和大于基准值元素的子数列排序。

递归到最底部时，数列的大小是零或一，也就是已经排序好了。这个算法一定会结束，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。

在简单的伪代码中，此算法可以被表示为：

原地（in-place）分区的版本

上面简单版本的缺点是，它需要Ω(n)的额外存储空间，也就跟归并排序一样不好。额外需要的内存空间配置，在实际上的实现，也会极度影响速度和缓存的性能。有一个比较复杂使用原地（in-place）分区算法的版本，且在好的基准选择上，平均可以达到O(log n )空间的使用复杂度。

这是原地分区算法，它分区了标示为"左边（left）"和"右边（right）"的序列部分，借由移动小于 a[pivotIndex] 的所有元素到子序列的开头，留下所有大于或等于的元素接在他们后面。在这个过程它也为基准元素找寻最后摆放的位置，也就是它回传的值。它暂时地把基准元素移到子序列的结尾，而不会被前述方式影响到。由于算法只使用交换，因此最后的数列与原先的数列拥有一样的元素。要注意的是，一个元素在到达它的最后位置前，可能会被交换很多次。

一旦我们有了这个分区算法，要写快速排列本身就很容易：

这个版本经常会被使用在命令式语言中，像是C语言。

优化的排序算法

快速排序是二叉查找树（二叉查找树）的一个空间最优化版本。不是循序地把数据项插入到一个明确的树中，而是由快速排序组织这些数据项到一个由递归调用所隐含的树中。这两个算法完全地产生相同的比较次数，但是顺序不同。对于排序算法的稳定性指标，原地分区版本的快速排序算法是不稳定的。其他变种是可以通过牺牲性能和空间来维护稳定性的。

快速排序的最直接竞争者是堆排序（Heapsort）。堆排序通常比快速排序稍微慢，但是最坏情况的运行时间总是O( n log n )。快速排序是经常比较快，除了introsort变化版本外，仍然有最坏情况性能的机会。如果事先知道堆排序将会是需要使用的，那么直接地使用堆排序比等待introsort再切换到它还要快。堆排序也拥有重要的特点，仅使用固定额外的空间（堆排序是原地排序），而即使是最佳的快速排序变化版本也需要Θ(log n )的空间。然而，堆排序需要有效率的随机存取才能变成可行。

快速排序也与归并排序（Mergesort）竞争，这是另外一种递归排序算法，但有坏情况O( n log n )运行时间的优势。不像快速排序或堆排序，归并排序是一个稳定排序，且可以轻易地被采用在链表（linked list）和存储在慢速访问媒体上像是磁盘存储或网络连接存储的非常巨大数列。尽管快速排序可以被重新改写使用在炼串列上，但是它通常会因为无法随机存取而导致差的基准选择。归并排序的主要缺点，是在最佳情况下需要Ω(n)额外的空间。

正规分析

从一开始快速排序平均需要花费O( n log n )时间的描述并不明显。但是不难观察到的是分区运算，数组的元素都会在每次循环中走访过一次，使用O( n )的时间。在使用结合（concatenation）的版本中，这项运算也是O( n )。

在最好的情况，每次我们运行一次分区，我们会把一个数列分为两个几近相等的片段。这个意思就是每次递归调用处理一半大小的数列。因此，在到达大小为一的数列前，我们只要作log n 次嵌套的调用。这个意思就是调用树的深度是O(log n )。但是在同一层次结构的两个程序调用中，不会处理到原来数列的相同部分；因此，程序调用的每一层次结构总共全部仅需要O( n )的时间（每个调用有某些共同的额外耗费，但是因为在每一层次结构仅仅只有O( n )个调用，这些被归纳在O( n )系数中）。结果是这个算法仅需使用O( n log n )时间。

另外一个方法是为T( n )设立一个递归关系式，也就是需要排序大小为 n 的数列所需要的时间。在最好的情况下，因为一个单独的快速排序调用牵涉了O( n )的工作，加上对 n/2 大小之数列的两个递归调用，这个关系式可以是：

解决这种关系式类型的标准数学归纳法技巧告诉我们T( n ) = O( n log n )。

事实上，并不需要把数列如此精确地分区；即使如果每个基准值将元素分开为99%在一边和1%在另一边，调用的深度仍然限制在100log n ，所以全部运行时间依然是O( n log n )。

然而，在最坏的情况是，两子数列拥有大各为1和 n -1，且调用树（call tree）变成为一个 n 个嵌套（nested）调用的线性连串（chain）。第 i 次调用作了O(n-i)的工作量，且 ∑ ∑ --> i = 0 n ( n − − --> i ) = O ( n 2 ) {\displaystyle \sum _{i=0}^{n}(n-i)=O(n^{2})} 递归关系式为：

这与插入排序和选择排序有相同的关系式，以及它被解为T( n ) = O(n )。

随机数快速排序的期望复杂度

随机数快速排序有一个值得注意的特性，在任意输入数据的状况下，它只需要O( n log n )的期望时间。是什么让随机的基准变成一个好的选择？

假设我们排序一个数列，然后把它分为四个部分。在中央的两个部分将会包含最好的基准值；他们的每一个至少都会比25%的元素大，且至少比25%的元素小。如果我们可以一致地从这两个中央的部分选出一个元素，在到达大小为1的数列前，我们可能最多仅需要把数列分区2log 2 n 次，产生一个O( n log n )算法。

不幸地，随机数选择只有一半的时间会从中间的部分选择。出人意外的事实是这样就已经足够好了。想像你正在翻转一枚硬币，一直翻转一直到有 k 次人头那面出现。尽管这需要很长的时间，平均来说只需要 2k 次翻动。且在100 k 次翻动中得不到 k 次人头那面的机会，是像天文数字一样的非常小。借由同样的论证，快速排序的递归平均只要2(2log 2 n )的调用深度就会终止。但是如果它的平均调用深度是O(log n )且每一阶的调用树状过程最多有 n 个元素，则全部完成的工作量平均上是乘积，也就是O( n log n )。

平均复杂度

即使如果我们无法随机地选择基准数值，对于它的输入之所有可能排列，快速排序仍然只需要O( n log n )时间。因为这个平均是简单地将输入之所有可能排列的时间加总起来，除以 n 这个因数，相当于从输入之中选择一个随机的排列。当我们这样作，基准值本质上就是随机的，导致这个算法与随机数快速排序有一样的运行时间。

更精确地说，对于输入顺序之所有排列情形的平均比较次数，可以借由解出这个递归关系式可以精确地算出来。

C ( n ) = n − − --> 1 + 1 n ∑ ∑ --> i = 0 n − − --> 1 ( C ( i ) + C ( n − − --> i − − --> 1 ) ) = 2 n ln ⁡ ⁡ --> n = 1.39 n log 2 ⁡ ⁡ --> n {\displaystyle C(n)=n-1+{\frac {1}{n}}\sum _{i=0}^{n-1}(C(i)+C(n-i-1))=2n\ln n=1.39n\log _{2}n} 。

在这里， n-1 是分区所使用的比较次数。因为基准值是相当均匀地落在排列好的数列次序之任何地方，总和就是所有可能分区的平均。

这个意思是，平均上快速排序比理想的比较次数，也就是最好情况下，只大约比较糟39%。这意味着，它比最坏情况较接近最好情况。这个快速的平均运行时间，是快速排序比其他排序算法有实际的优势之另一个原因。

空间复杂度

被快速排序所使用的空间，依照使用的版本而定。使用原地（in-place）分区的快速排序版本，在任何递归调用前，仅会使用固定的額外空間。然而，如果需要产生O(log n )嵌套递归调用，它需要在他们每一个存储一个固定数量的信息。因为最好的情况最多需要O(log n )次的嵌套递归调用，所以它需要O(log n )的空间。最坏情况下需要O( n )次嵌套递归调用，因此需要O( n )的空间。

然而我们在这里省略一些小的细节。如果我们考虑排序任意很长的数列，我们必须要记住我们的变量像是 left 和 right ，不再被认为是占据固定的空间；也需要O(log n )对原来一个 n 项的数列作索引。因为我们在每一个堆栈框架中都有像这些的变量，实际上快速排序在最好跟平均的情况下，需要O(log n )空间的比特数，以及最坏情况下O( n log n )的空间。然而，这并不会太可怕，因为如果一个数列大部分都是不同的元素，那么数列本身也会占据O( n log n )的空间字节。

非原地版本的快速排序，在它的任何递归调用前需要使用O( n )空间。在最好的情况下，它的空间仍然限制在O( n )，因为递归的每一阶中，使用与上一次所使用最多空间的一半，且

它的最坏情况是很恐怖的，需要

空间，远比数列本身还多。如果这些数列元素本身自己不是固定的大小，这个问题会变得更大；举例来说，如果数列元素的大部分都是不同的，每一个将会需要大约O(log n )为原来存储，导致最好情况是O( n log n )和最坏情况是O( n log n )的空间需求。

选择的关连性

选择算法（selection algorithm）可以选取一个数列的第 k 个最小值；一般而言这是比排序还简单的问题。一个简单但是有效率的选择算法与快速排序的作法相当类似，除了对两个子数列都作递归调用外，它仅仅针对包含想要的元素之子数列作单一的结尾递归（tail recursive）调用。这个小改变降低了平均复杂度到线性或是Θ( n )时间，且让它成为一个原地算法。这个算法的一种变化版本，可以让最坏情况下降为O( n )（参考选择算法来得到更多信息）。

相反地，一旦我们知道一个最坏情况的O( n )选择算法是可以利用的，我们在快速排序的每一步可以用它来找到理想的基准（中位数），得到一种最坏情况下O( n log n )运行时间的变化版本。然而在实际的实现中，这种版本一般而言相当慢。

实现示例

C语言

迭代法

typedefstruct_Range{intstart,end;}Range;Rangenew_Range(ints,inte){Ranger;r.start=s;r.end=e;returnr;}voidswap(int*x,int*y){intt=*x;*x=*y;*y=t;}voidquick_sort(intarr[],constintlen){if(len=range.end)continue;intmid=arr[range.end];intleft=range.start,right=range.end-1;while(left<right){while(arr[left]<mid&&left=mid&&left=arr[range.end])swap(&arr[left],&arr[range.end]);elseleft++;r[p++]=new_Range(range.start,left-1);r[p++]=new_Range(left+1,range.end);}}

递归法

voidswap(int*x,int*y){intt=*x;*x=*y;*y=t;}voidquick_sort_recursive(intarr[],intstart,intend){if(start>=end)return;//這是為了防止宣告堆疊陣列時當機intmid=arr[end];intleft=start,right=end-1;while(left<right){while(arr[left]<mid&&left=mid&&left=arr[end])swap(&arr[left],&arr[end]);elseleft++;if(left){quick_sort_recursive(arr,start,left-1);}quick_sort_recursive(arr,left+1,end);}voidquick_sort(intarr[],intlen){quick_sort_recursive(arr,0,len-1);}

C++

迭代法

//参考：ructRange{intstart,end;Range(ints=0,inte=0){start=s,end=e;}};template//整數或浮點數皆可使用,若要使用物件(class)時必須設定"小於"()、"不小於"(>=)的運算子功能voidquick_sort(Tarr[],constintlen){if(len=range.end)continue;Tmid=arr[range.end];intleft=range.start,right=range.end-1;while(left<right){while(arr[left]<mid&&left=mid&&left=arr[range.end])std::swap(arr[left],arr[range.end]);elseleft++;r[p++]=Range(range.start,left-1);r[p++]=Range(left+1,range.end);}}

递归法

templatevoidquick_sort_recursive(Tarr[],intstart,intend){if(start>=end)return;Tmid=arr[end];intleft=start,right=end-1;while(left<right){while(arr[left]<mid&&left=mid&&left=arr[end])std::swap(arr[left],arr[end]);elseleft++;quick_sort_recursive(arr,start,left-1);quick_sort_recursive(arr,left+1,end);}template//整數或浮點數皆可使用,若要使用物件(class)時必須設定"小於"()、"不小於"(>=)的運算子功能voidquick_sort(Tarr[],intlen){quick_sort_recursive(arr,0,len-1);}

funcqsort(data[]int){iflen(data)<=1{return}mid,i:=data[0],1head,tail:=0,len(data)-1fori=1;imid{data[i],data[tail]=data[tail],data[i]tail--}else{data[i],data[head]=data[head],data[i]head++i++}}data[head]=midqsort(data[:head])qsort(data[head+1:])}

scheme

#langracket;;快速排序(define quick-sort(λ(s)(if (< (length s)2)s(append(quick-sort(filter(λ(e)( e(lasts)))s))))))

Common Lisp

(defunfilter-<(lstpivot)(remove-if-not(lambda(x)(<xpivot))lst))(defunquick-sort(lst)(if((cdrlst))lst(let((pivot(carlst))(else(cdrlst)))(append(quick-sort(filter-<elsepivot))(listpivot)(quick-sort(set-differenceelse(filter-<elsepivot)))))))

Erlang

qsort([])->[];qsort([Head|Rest])->qsort([X||XRest,X=Head]).

Java

classquick_sort{int[]arr;privatevoidswap(intx,inty){inttemp=arr[x];arr[x]=arr[y];arr[y]=temp;}privatevoidquick_sort_recursive(intstart,intend){if(start>=end)return;intmid=arr[end];intleft=start,right=end-1;while(left<right){while(arr[left]<=mid&&left=mid&&left=arr[end])swap(left,end);elseleft++;quick_sort_recursive(start,left-1);quick_sort_recursive(left+1,end);}publicvoidsort(int[]arrin){arr=arrin;quick_sort_recursive(0,arr.length-1);}}

Perl

subqsort{return()unless@_;(qsort(grep{$_=$_[0]}@_[1..$#_]));}

Python

1 defquicksort(a):2 iflen(a)<=1:3 returna# 如果a為一位數則直接傳回a4 l=[xforxina[1:]ifxa[0]]# 輸出排序後的比a[0]大的數列6 returnquicksort(l)+[a[0]]+quicksort(r)

Joy

PHP

从尾端取元素作为比较基准

functionquick_sort($arr){$len=count($arr);if($len<=1)return$arr;$left=$right=array();$mid_value=$arr[0];for($i=1;$i<$len;$i++)if($arr[$i]<$mid_value)$left[]=$arr[$i];else$right[]=$arr[$i];returnarray_merge(quick_sort($left),(array)$mid_value,quick_sort($right));}

从正中间取元素作为比较基准

functionquick_sort($arr){$len=count($arr);if($len>1;$mid_value=$arr[$mid_index];for($i=0;$i<$len;$i++){if($i==$mid_index)continue;if($arr[$i]<$mid_value)$left[]=$arr[$i];else$right[]=$arr[$i];}returnarray_merge(quick_sort($left),(array)$mid_value,quick_sort($right));}$arr=array(21,34,3,32,82,55,89,50,37,5,64,35,9,70);$arr=quick_sort($arr);for($i=0;$i<count($arr);$i++){echo$arr[$i]." ";}

Haskell

sort::(Orda)=>[a]->[a]sort[]=[]sort(pivot:rest)=sort[y|yrest,y=pivot]

Prolog

Ruby

defquick_sort(array)returnarrayifarray.size<2left,right=array[1..-1].partition{|y|y<=array.first}quick_sort(left)+[array.first]+quick_sort(right)end

Standard ML

This example demonstrates the use of an arbitrary predicate in a functional language.

Pascal

procedurequickSort(vara:arrayofinteger;l,r:Integer);vari,j,x:integer;beginifl>=rthenexit;i:=l;j:=r;x:=a[i];whilei<=jdobeginwhile(ix)dodec(j);ifi<jthenbegina[i]:=a[j];inc(i);end;while(i<j)and(a[i]<x)doinc(i);ifi<jthenbegina[j]:=a[i];dec(j);end;a[i]:=x;quicksort(a,l,i-1);quicksort(a,i+1,r);end;end;

或者

procedurequicksort(vara:arrayofinteger;l,r:integer);vari,j,x,t:integer;begini:=l;j:=r;x:=a[(l+r)div2];repeatwhilea[i]xdodec(j);ifij;ifi<rthenquicksort(a,i,r);ifl<jthenquicksort(a,l,j);end;

publicstaticvoidSort(int[]numbers){Sort(numbers,0,numbers.Length-1);}privatestaticvoidSort(int[]numbers,intleft,intright){if(left<right){intmiddle=numbers[(left+right)/2];inti=left-1;intj=right+1;while(true){while(numbers[++i]middle);if(i>=j)break;Swap(numbers,i,j);}Sort(numbers,left,i-1);Sort(numbers,j+1,right);}}privatestaticvoidSwap(int[]numbers,inti,intj){intnumber=numbers[i];numbers[i]=numbers[j];numbers[j]=number;}

VB.Net

PublicSharedSubSort(numbersAsInteger())Sort(numbers,0,numbers.Length-1)EndSubPrivateSharedSubSort(numbersAsInteger(),leftAsInteger,rightAsInteger)Ifleft<rightThenDimmiddleAsInteger=numbers((left+right)\2)DimiAsInteger=left-1DimjAsInteger=right+1WhileTrueDoi+=1LoopWhilenumbers(i)=middleIfi>=jThenExitWhileEndIfSwap(numbers,i,j)EndWhileSort(numbers,left,i-1)Sort(numbers,j+1,right)EndIfEndSubPrivateSharedSubSwap(numbersAsInteger(),iAsInteger,jAsInteger)DimnumberAsInteger=numbers(i)numbers(i)=numbers(j)numbers(j)=numberEndSub

ActionScript

publicfunction qSort(arr:Array):void{quickSort(arr,0,arr.length-1);}privatefunction quickSort(data:Array,left:int,right:int):void{vartemp:Number=data[left];varp:int=left;vari:int=left,j:int=right;while(i=temp&&j>=p)j--;if(j>=p){data[p]=data[j];p=j;}while(data[i]<=temp&&i<=p)i++;if(i1){quickSort(data,left,p-1);}if(right-p>1){quickSort(data,p+1,right);}}

JavaScript

Array.prototype.quick_sort=function(){varlen=this.length;if(len<=1)returnthis.slice(0);varleft=[];varright=[];varmid=[this[0]];for(vari=1;i<len;i++)if(this[i]<mid[0])left.push(this[i]);elseright.push(this[i]);returnleft.quick_sort().concat(mid.concat(right.quick_sort()));};vararr=[5,3,7,4,1,9,8,6,2];arr=arr.quick_sort();for(i=0;i<arr.length;i++)document.body.innerHTML+=arr[i]+" ";document.body.innerHTML+="";

参考

Hoare, C. A. R. "Partition: Algorithm 63," "Quicksort: Algorithm 64," and "Find: Algorithm 65." Comm. ACM 4, 321-322, 1961

R. Sedgewick. Implementing quicksort programs, Communications of the ACM, 21(10):847857, 1978.

David Musser. Introspective Sorting and Selection Algorithms, Software Practice and Experience vol 27, number 8, pages 983-993, 1997

A. LaMarca and R. E. Ladner. "The Influence of Caches on the Performance of Sorting." Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 1997. pp. 370–379.

Faron Moller.Analysis of Quicksort. CS 332: Designing Algorithms. Department of Computer Science, University of Wales Swansea.

Steven Skiena.Lecture 5 - quicksort. CSE 373/548 - Analysis of Algorithms. Department of Computer Science. SUNY Stony Brook.

脚注

1. David M. W. Powers.Parallelized Quicksort with Optimal Speedup. Proceedings of International Conference on Parallel Computing Technologies . Novosibirsk. 1991.

免责声明：以上内容版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。感谢每一位辛勤著写的作者，感谢每一位的分享。

——— 没有了 ———