快速排序是对冒泡排序的一种改进。它的基本思想是：通过一次排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一不部分的所有数据都要小，然后再按次方法对这两部分数据分别进行快速排序，整个排序过程可以递归或者非递归进行，以此达到整个数据变成有序序列。

实例

functionquickSort(arr,left,right){varlen=arr.length,partitionIndex,left=typeofleft!='number'?0:left,right=typeofright!='number'?len-1:right;if(leftreturnarr;}functionpartition(arr,left,right){//分区操作varpivot=left,//设定基准值（pivot）index=pivot+1;for(vari=index;iif(arr[i]returnindex-1;}functionswap(arr,i,j){vartemp=arr[i];arr[i]=arr[j];arr[j]=temp;}functionpartition2(arr,low,high){letpivot=arr[low];while(lowwhile(lowpivot){--high;}arr[low]=arr[high];while(lowreturnlow;}functionquickSort2(arr,low,high){if(lowletpivot=partition2(arr,low,high);quickSort2(arr,low,pivot-1);quickSort2(arr,pivot+1,high);}returnarr;}Python

实例

defquickSort(arr,left=None,right=None):left=0ifnotisinstance(left,(int,float))elseleftright=len(arr)-1ifnotisinstance(right,(int,float))elserightifleftreturnarrdefpartition(arr,left,right):pivot=leftindex=pivot+1i=indexwhileiifarr[i]returnindex-1defswap(arr,i,j):arr[i],arr[j]=arr[j],arr[i]Go

实例

funcquickSort(arr[]int)[]int{return_quickSort(arr,0,len(arr)-1)}func_quickSort(arr[]int,left,rightint)[]int{ifleftreturnarr}funcpartition(arr[]int,left,rightint)int{pivot:=leftindex:=pivot+1fori:=index;iifarr[i]returnindex-1}funcswap(arr[]int,i,jint){arr[i],arr[j]=arr[j],arr[i]}C++

实例

//严蔚敏《数据结构》标准分割函数Paritition1(intA[],intlow,inthigh){intpivot=A[low];while(lowwhile(low=pivot){--high;}A[low]=A[high];while(lowreturnlow;}voidQuickSort(intA[],intlow,inthigh)//快排母函数{if(lowJava

实例

publicclassQuickSortimplementsIArraySort{@Overridepublicint[]sort(int[]sourceArray)throwsException{//对arr进行拷贝，不改变参数内容int[]arr=Arrays.copyOf(sourceArray,sourceArray.length);returnquickSort(arr,0,arr.length-1);}privateint[]quickSort(int[]arr,intleft,intright){if(leftreturnarr;}privateintpartition(int[]arr,intleft,intright){//设定基准值（pivot）intpivot=left;intindex=pivot+1;for(inti=index;iif(arr[i]returnindex-1;}privatevoidswap(int[]arr,inti,intj){inttemp=arr[i];arr[i]=arr[j];arr[j]=temp;}}PHP

实例

functionquickSort($arr){if(count($arr)return$arr;$middle=$arr[0];$leftArray=array();$rightArray=array();for($i=1;$i$arr);$i++){if($arr[$i]>$middle)$rightArray[]=$arr[$i];else$leftArray[]=$arr[$i];}$leftArray=quickSort($leftArray);$leftArray[]=$middle;$rightArray=quickSort($rightArray);returnarray_merge($leftArray,$rightArray);}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(lenreturn;//避免len等於負值時引發段錯誤（SegmentFault）//r[]模擬列表,p為數量,r[p++]為push,r[--p]為pop且取得元素Ranger[len];intp=0;r[p++]=new_Range(0,len-1);while(p){Rangerange=r[--p];if(range.start>=range.end)continue;intmid=arr[(range.start+range.end)/2];//選取中間點為基準點intleft=range.start,right=range.end;do{while(arr[left]while(arr[right]>mid)--right;//檢測基準點右側是否符合要求if(leftwhile(leftif(range.startif(range.end>left)r[p++]=new_Range(left,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(leftwhile(arr[left]while(arr[right]>=mid&&leftif(arr[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++

函数法

sort(a,a+n);//排序a[0]-a[n-1]的所有数.

迭代法

实例

//参考：http://www.dutor.net/index.php/2011/04/recursive-iterative-quick-sort/structRange{intstart,end;Range(ints=0,inte=0){start=s,end=e;}};template//整數或浮點數皆可使用,若要使用物件(class)時必須設定"小於"("大於"(>)、"不小於"(>=)的運算子功能voidquick_sort(Tarr[],constintlen){if(lenreturn;//避免len等於負值時宣告堆疊陣列當機//r[]模擬堆疊,p為數量,r[p++]為push,r[--p]為pop且取得元素Ranger[len];intp=0;r[p++]=Range(0,len-1);while(p){Rangerange=r[--p];if(range.start>=range.end)continue;Tmid=arr[range.end];intleft=range.start,right=range.end-1;while(leftwhile(arr[left]while(arr[right]>=mid&&leftif(arr[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(leftwhile(arr[left]while(arr[right]>=mid&&leftif(arr[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);}