快速排序算法

基本思想

快速排序采用的是分治思想，即在一個(gè)無(wú)序的序列中選取一個(gè)任意的基準(zhǔn)元素pivot，利用pivot將待排序的序列分成兩部分，前面部分元素均小于或等于基準(zhǔn)元素，后面部分均大于或等于基準(zhǔn)元素，然后采用遞歸的方法分別對(duì)前后兩部分重復(fù)上述操作，直到將無(wú)序序列排列成有序序列。5

排序流程

快速排序算法通過(guò)多次比較和交換來(lái)實(shí)現(xiàn)排序，其排序流程如下：2

1、首先設(shè)定一個(gè)分界值，通過(guò)該分界值將數(shù)組分成左右兩部分。2

2、將大于或等于分界值的數(shù)據(jù)集中到數(shù)組右邊，小于分界值的數(shù)據(jù)集中到數(shù)組的左邊。此時(shí)，左邊部分中各元素都小于分界值，而右邊部分中各元素都大于或等于分界值。2

3、然后，左邊和右邊的數(shù)據(jù)可以獨(dú)立排序。對(duì)于左側(cè)的數(shù)組數(shù)據(jù)，又可以取一個(gè)分界值，將該部分?jǐn)?shù)據(jù)分成左右兩部分，同樣在左邊放置較小值，右邊放置較大值。右側(cè)的數(shù)組數(shù)據(jù)也可以做類似處理。2

4、重復(fù)上述過(guò)程，可以看出，這是一個(gè)遞歸定義。通過(guò)遞歸將左側(cè)部分排好序后，再遞歸排好右側(cè)部分的順序。當(dāng)左、右兩個(gè)部分各數(shù)據(jù)排序完成后，整個(gè)數(shù)組的排序也就完成了。2

排序步驟

原理

設(shè)要排序的數(shù)組是A[0]……A[N-1]，首先任意選取一個(gè)數(shù)據(jù)（通常選用數(shù)組的第一個(gè)數(shù)）作為關(guān)鍵數(shù)據(jù)，然后將所有比它小的數(shù)都放到它左邊，所有比它大的數(shù)都放到它右邊，這個(gè)過(guò)程稱為一趟快速排序。值得注意的是，快速排序不是一種穩(wěn)定的排序算法，也就是說(shuō)，多個(gè)相同的值的相對(duì)位置也許會(huì)在算法結(jié)束時(shí)產(chǎn)生變動(dòng)。1

一趟快速排序的算法是：1

（1）設(shè)置兩個(gè)變量i、j，排序開(kāi)始的時(shí)候：i=0，j=N-1；1

（2）以第一個(gè)數(shù)組元素作為關(guān)鍵數(shù)據(jù)，賦值給key，即key=A[0]；1

（3）從j開(kāi)始向前搜索，即由后開(kāi)始向前搜索(j--)，找到第一個(gè)小于key的值A(chǔ)[j]，將A[j]和A[i]的值交換；1

（4）從i開(kāi)始向后搜索，即由前開(kāi)始向后搜索(i++)，找到第一個(gè)大于key的A[i]，將A[i]和A[j]的值交換；1

（5）重復(fù)第3、4步，直到i==j； （3,4步中，沒(méi)找到符合條件的值，即3中A[j]不小于key,4中A[i]不大于key的時(shí)候改變j、i的值，使得j=j-1，i=i+1，直至找到為止。找到符合條件的值，進(jìn)行交換的時(shí)候i， j指針位置不變。另外，i==j這一過(guò)程一定正好是i+或j-完成的時(shí)候，此時(shí)令循環(huán)結(jié)束）。1

排序演示

假設(shè)一開(kāi)始序列{xi}是：5，3，7，6，4，1，0，2，9，10，8。

此時(shí)，ref=5，i=1，j=11，從后往前找，第一個(gè)比5小的數(shù)是x8=2，因此序列為：2，3，7，6，4，1，0，5，9，10，8。

此時(shí)i=1，j=8，從前往后找，第一個(gè)比5大的數(shù)是x3=7，因此序列為：2，3，5，6，4，1，0，7，9，10，8。

此時(shí)，i=3，j=8，從第8位往前找，第一個(gè)比5小的數(shù)是x7=0，因此：2，3，0，6，4，1，5，7，9，10，8。

此時(shí)，i=3，j=7，從第3位往后找，第一個(gè)比5大的數(shù)是x4=6，因此：2，3，0，5，4，1，6，7，9，10，8。

此時(shí)，i=4，j=7，從第7位往前找，第一個(gè)比5小的數(shù)是x6=1，因此：2，3，0，1，4，5，6，7，9，10，8。

此時(shí)，i=4，j=6，從第4位往后找，直到第6位才有比5大的數(shù)，這時(shí)，i=j=6，ref成為一條分界線，它之前的數(shù)都比它小，之后的數(shù)都比它大，對(duì)于前后兩部分?jǐn)?shù)，可以采用同樣的方法來(lái)排序。3

程序調(diào)用舉例

用法:3

<pre data-lang="clike">void qsort(void *base, int nelem, int width, int (*fcmp)(const void *,const void *));

參數(shù)：

1、待排序數(shù)組首地址；3

2、數(shù)組中待排序元素?cái)?shù)量；3

3、各元素的占用空間大?。?

4、指向函數(shù)的指針，用于確定排序的順序。3

示例代碼

GO

<pre data-lang="cpp">//?第一種寫(xiě)法func?quickSort(values?[]int,?left,?right?int)?{????temp?:=?values[left]????p?:=?left????i,?j?:=?left,?right????for?i?<=?j?{????????for?j?>=?p?&&?values[j]?>=?temp?{????????????j--????????}????????if?j?>=?p?{????????????values[p]?=?values[j]????????????p?=?j????????}????????for?i?<=?p?&&?values[i]?<=?temp?{????????????i++????????}????????if?i?<=?p?{????????????values[p]?=?values[i]????????????p?=?i????????}????}????values[p]?=?temp????if?p-left?>?1?{????????quickSort(values,?left,?p-1)????}????if?right-p?>?1?{????????quickSort(values,?p+1,?right)????}}func?QuickSort(values?[]int)?{????if?len(values)?<=?1?{????????return????}????quickSort(values,?0,?len(values)-1)}//?第二種寫(xiě)法func?Quick2Sort(values?[]int)?{????if?len(values)?<=?1?{????????return????}????mid,?i?:=?values[0],?1????head,?tail?:=?0,?len(values)-1????for?head?<?tail?{????????fmt.Println(values)????????if?values[i]?>?mid?{????????????values[i],?values[tail]?=?values[tail],?values[i]????????????tail--????????}?else?{????????????values[i],?values[head]?=?values[head],?values[i]????????????head++????????????i++????????}????}????values[head]?=?mid????Quick2Sort(values[:head])????Quick2Sort(values[head+1:])}//?第三種寫(xiě)法func?Quick3Sort(a?[]int,left?int,?right?int)??{????if?left?>=?right?{????????return????}????explodeIndex?:=?left????for?i?:=?left?+?1;?i?<=?right?;?i++?{????????if?a[left]?>=?a[i]{????????????//分割位定位++????????????explodeIndex?++;????????????a[i],a[explodeIndex]?=?a[explodeIndex],a[i]????????}????}????//起始位和分割位????a[left],?a[explodeIndex]?=?a[explodeIndex],a[left]????Quick3Sort(a,left,explodeIndex?-?1)????Quick3Sort(a,explodeIndex?+?1,right)}

Ruby

<pre data-lang="ruby">def?quick_sort(a)????(x=a.pop)???quick_sort(a.select?{?|i|?i?<=?x?})?+?[x]?+?quick_sort(a.select?{?|i|?i?>?x?})?:?[]end

Erlang語(yǔ)言

<pre data-lang="erlang">超簡(jiǎn)短實(shí)現(xiàn)：q_sort([])->[];q_sort([H|R])->q_sort([X||X<-R,X<H])++[H]++q_sort([X||X<-R,X>=H]).

Haskell語(yǔ)言

<pre data-lang="erlang">q_sort?n=case?n?of????[]->[]????(x:xs)->q_sort?[a|a<-xs,a<=x]++[x]++q_sort?[a|a<-xs,a>x]

C++語(yǔ)言

<pre data-lang="cpp">#include?<iostream>using?namespace?std;void?Qsort(int?arr[],?int?low,?int?high){????if?(high?<=?low)?return;????int?i?=?low;????int?j?=?high;????int?key?=?arr[low];????while?(true)????{????????/*從左向右找比key大的值*/????????while?(arr[i]?<=?key)????????{  i++;????????????if?(i?==?high){????????????????break;????????????}????????}????????/*從右向左找比key小的值*/????????while?(arr[j]?>=?key)????????{  j--;????????????if?(j?==?low){????????????????break;????????????}????????}????????if?(i?>=?j)?break;????????/*交換i,j對(duì)應(yīng)的值*/????????int?temp?=?arr[i];????????arr[i]?=?arr[j];????????arr[j]?=?temp;????}????/*中樞值與j對(duì)應(yīng)值交換*/????arr[low]?=?arr[j];????arr[j]?=?key;????Qsort(arr,?low,?j?-?1);????Qsort(arr,?j?+?1,?high);}int?main(){????int?a[]?=?{57,?68,?59,?52,?72,?28,?96,?33,?24};????Qsort(a,?0,?sizeof(a)?/?sizeof(a[0])?-?1);/*這里原文第三個(gè)參數(shù)要減1否則內(nèi)存越界*/????for(int?i?=?0;?i?<?sizeof(a)?/?sizeof(a[0]);?i++) {????????cout?<<?a[i]?<<?" ";????}????????return?0;}/*參考數(shù)據(jù)結(jié)構(gòu)p274(清華大學(xué)出版社，嚴(yán)蔚敏)*/

C語(yǔ)言版本

<pre data-lang="cpp">void quickSort(int *number, int first, int last) {int i, j, pivot;int temp;if (first<last) {pivot = first;i = first;j = last;while (i<j) {while (number[i] <= number[pivot] && i<last)i++;while (number[j]>number[pivot])j--;if (i<j) {temp = number[i];number[i] = number[j];number[j] = temp;}}temp = number[pivot];number[pivot] = number[j];number[j] = temp;quickSort(number, first, j - 1);quickSort(number, j + 1, last);}}

Swift

<pre data-lang="cpp">func?quickSort(a:?inout?[Int],?low:?Int,?high:?Int)?{????if?low?>=?high?{?//?遞歸結(jié)束條件????????return????}????var?i?=?low????var?j?=?high????let?key?=?a[i]????while?i?<?j?{????????//?從右邊開(kāi)始比較，比key大的數(shù)位置不變????????while?i?<?j?&&?a[j]?>=?key?{????????????j?-=?1????????}????????//?只要出現(xiàn)一個(gè)比key小的數(shù)，將這個(gè)數(shù)放入左邊i的位置????????a[i]?=?a[j]????????//?從左邊開(kāi)始比較，比key小的數(shù)位置不變????????while?i?<?j?&&?a[i]?<=?key?{????????????i?+=?1????????}????????//?只要出現(xiàn)一個(gè)比key大的數(shù)，將這個(gè)數(shù)放入右邊j的位置????????a[j]?=?a[i]????}????a[i]?=?key?//?將key放入i的位置，則左側(cè)數(shù)都比key小，右側(cè)數(shù)都比key大????quickSort(a:?&a,?low:?low,?high:?i?-?1)?//?左遞歸????quickSort(a:?&a,?low:?i?+?1,?high:?high)?//?右遞歸}//?示例var?m?=?[2,3,5,7,1,4,6,15,5,2,7,9,10,15,9,17,12]quickSort(a:?&m,?low:?0,?high:?m.count?-?1)print(m)//?結(jié)果：[1,?2,?2,?3,?4,?5,?5,?6,?7,?7,?9,?9,?10,?12,?15,?15,?17]

Objective-C

<pre data-lang="cpp">+?(void)quickSort:(NSMutableArray?*)m?low:(int)low?high:(int)high{????if?(low?>=?high)?{????????return;????}????int?i?=?low;????int?j?=?high;????id?key?=?m[i];????while?(i<j)?{????????while?(i<j?&&?[m[j]?intValue]?>=?[key?intValue])?{????????????j--;????????}????????if?(i?==?j)?{?//?當(dāng)key是目前最小的數(shù)時(shí)，會(huì)出現(xiàn)i=j的情況，????????????break;????????}????????m[i++]?=?m[j];?//?i++?會(huì)減少一次m[i]和key的比較????????while?(i?<?j?&&?[m[i]?intValue]?<=?[key?intValue])?{????????????i++;????????}??????????if?(i?==?j)?{?//?當(dāng)key是目前最大的數(shù)時(shí)(m[j]的前面)，會(huì)出現(xiàn)i=j的情況????????????break;????????}????????m[j--]?=?m[i];?//j--?會(huì)減少一次m[j]和key的比較????}????m[i]?=?key;????[self?quickSort:?m?low:?low?high:?i-1];????[self?quickSort:?m?low:?i+1?high:?high];????//?NSLog(@"快速排序?%@",m);}

JavaScript

<pre data-lang="js">const?quickSort?=?(array)?=>?{?const?sort?=?(arr,?left?=?0,?right?=?arr.length?-?1)?=>?{??if?(left?>=?right)?{//如果左邊的索引大于等于右邊的索引說(shuō)明整理完畢???return??}?let?i?=?left?let?j?=?right?const?baseVal?=?arr[j]?//?取無(wú)序數(shù)組最后一個(gè)數(shù)為基準(zhǔn)值?while?(i?<?j)?{//把所有比基準(zhǔn)值小的數(shù)放在左邊大的數(shù)放在右邊??while?(i?<?j?&&?arr[i]?<=?baseVal)?{?//找到一個(gè)比基準(zhǔn)值大的數(shù)交換???i++??}??arr[j]?=?arr[i]?//?將較大的值放在右邊如果沒(méi)有比基準(zhǔn)值大的數(shù)就是將自己賦值給自己（i?等于?j）??while?(j?>?i?&&?arr[j]?>=?baseVal)?{?//找到一個(gè)比基準(zhǔn)值小的數(shù)交換???j--?}??arr[i]?=?arr[j]?//?將較小的值放在左邊如果沒(méi)有找到比基準(zhǔn)值小的數(shù)就是將自己賦值給自己（i?等于?j）?}?arr[j]?=?baseVal?//?將基準(zhǔn)值放至中央位置完成一次循環(huán)（這時(shí)候?j?等于?i?）?sort(arr,?left,?j-1)?//?將左邊的無(wú)序數(shù)組重復(fù)上面的操作?sort(arr,?j+1,?right)?//?將右邊的無(wú)序數(shù)組重復(fù)上面的操作?}?const?newArr?=?array.concat()?//?為了保證這個(gè)函數(shù)是純函數(shù)拷貝一次數(shù)組?sort(newArr)?return?newArr}// 方法二：let _quickSort = (left, right, nums) => { let swap = (left, right, nums) => { let temp = nums[left] nums[left] = nums[right] nums[right] = temp } if (left <= right) { let val = nums[left] let [i, j] = [left, right] while (i < j) {  while (i < j && nums[j] > val) {  j--  }  while (i < j && nums[i] < val) {  i++  }  if (i < j) {  swap(i, j , nums)  } } nums[i] = val _quickSort(left, i - 1, nums) _quickSort(i + 1, right, nums) }}let quickSort = (...numbers) => { _quickSort(0, numbers.length - 1, numbers) return numbers}console.log(quickSort(1, 20, 9, 13, 59, 19, 98))

Java

<pre data-lang="java">/** * 入口函數(shù)（遞歸方法），算法的調(diào)用從這里開(kāi)始。 */public void quickSort(int[] arr, int startIndex, int endIndex) { if (startIndex >= endIndex) {  return; } // 核心算法部分：分別介紹 雙邊指針（交換法），雙邊指針（挖坑法），單邊指針 int pivotIndex = doublePointerSwap(arr, startIndex, endIndex); // int pivotIndex = doublePointerHole(arr, startIndex, endIndex); // int pivotIndex = singlePointer(arr, startIndex, endIndex); // 用分界值下標(biāo)區(qū)分出左右區(qū)間，進(jìn)行遞歸調(diào)用 quickSort(arr, startIndex, pivotIndex - 1); quickSort(arr, pivotIndex + 1, endIndex);}/** * 雙邊指針（交換法） * 思路： * 記錄分界值 pivot，創(chuàng)建左右指針（記錄下標(biāo)）。 * （分界值選擇方式有：首元素，隨機(jī)選取，三數(shù)取中法） * * 首先從右向左找出比pivot小的數(shù)據(jù)， * 然后從左向右找出比pivot大的數(shù)據(jù)， * 左右指針數(shù)據(jù)交換，進(jìn)入下次循環(huán)。 * * 結(jié)束循環(huán)后將當(dāng)前指針數(shù)據(jù)與分界值互換， * 返回當(dāng)前指針下標(biāo)（即分界值下標(biāo)） */private int doublePointerSwap(int[] arr, int startIndex, int endIndex) { int pivot = arr[startIndex]; int leftPoint = startIndex; int rightPoint = endIndex; while (leftPoint < rightPoint) {  // 從右向左找出比pivot小的數(shù)據(jù)  while (leftPoint < rightPoint    && arr[rightPoint] > pivot) {   rightPoint--;  }  // 從左向右找出比pivot大的數(shù)據(jù)  while (leftPoint < rightPoint    && arr[leftPoint] <= pivot) {   leftPoint++;  }  // 沒(méi)有過(guò)界則交換  if (leftPoint < rightPoint) {   int temp = arr[leftPoint];   arr[leftPoint] = arr[rightPoint];   arr[rightPoint] = temp;  } } // 最終將分界值與當(dāng)前指針數(shù)據(jù)交換 arr[startIndex] = arr[rightPoint]; arr[rightPoint] = pivot; // 返回分界值所在下標(biāo) return rightPoint;}/** * 雙邊指針（挖坑法） * 思路： * 創(chuàng)建左右指針。 * 記錄左指針數(shù)據(jù)為分界值 pivot， * 此時(shí)左指針視為"坑"，里面的數(shù)據(jù)可以被覆蓋。 * * 首先從右向左找出比pivot小的數(shù)據(jù)， * 找到后立即放入左邊坑中，當(dāng)前位置變?yōu)樾碌?quot;坑"， * 然后從左向右找出比pivot大的數(shù)據(jù)， * 找到后立即放入右邊坑中，當(dāng)前位置變?yōu)樾碌?quot;坑"， * * 結(jié)束循環(huán)后將最開(kāi)始存儲(chǔ)的分界值放入當(dāng)前的"坑"中， * 返回當(dāng)前"坑"下標(biāo)（即分界值下標(biāo)） */private int doublePointerHole(int[] arr, int startIndex, int endIndex) { int pivot = arr[startIndex]; int leftPoint = startIndex; int rightPoint = endIndex; while (leftPoint < rightPoint) {  // 從右向左找出比pivot小的數(shù)據(jù)，  while (leftPoint < rightPoint    && arr[rightPoint] > pivot) {   rightPoint--;  }  // 找到后立即放入左邊坑中，當(dāng)前位置變?yōu)樾碌?quot;坑"  if (leftPoint < rightPoint) {   arr[leftPoint] = arr[rightPoint];   leftPoint++;  }  // 從左向右找出比pivot大的數(shù)據(jù)  while (leftPoint < rightPoint    && arr[leftPoint] <= pivot) {   leftPoint++;  }  // 找到后立即放入右邊坑中，當(dāng)前位置變?yōu)樾碌?quot;坑"  if (leftPoint < rightPoint) {   arr[rightPoint] = arr[leftPoint];   rightPoint--;  } } // 將最開(kāi)始存儲(chǔ)的分界值放入當(dāng)前的"坑"中 arr[rightPoint] = pivot; return rightPoint;}/** * 單邊指針 * 思路： * 記錄首元素為分界值 pivot, 創(chuàng)建標(biāo)記 mark 指針。 * 循環(huán)遍歷與分界值對(duì)比。 * 比分界值小，則 mark++ 后與之互換。 * 結(jié)束循環(huán)后，將首元素分界值與當(dāng)前mark互換。 * 返回 mark 下標(biāo)為分界值下標(biāo)。 */private int singlePointer(int[] arr, int startIndex, int endIndex) { int pivot = arr[startIndex]; int markPoint = startIndex; for (int i = startIndex + 1; i <= endIndex; i++) {  // 如果比分界值小，則 mark++ 后互換。  if (arr[i] < pivot) {   markPoint++;   int temp = arr[markPoint];   arr[markPoint] = arr[i];   arr[i] = temp;  } } // 將首元素分界值與當(dāng)前mark互換 arr[startIndex] = arr[markPoint]; arr[markPoint] = pivot; return markPoint;}

C#

<pre data-lang="c#">????using?System;?????using?System.Collections.Generic;?????using?System.Linq;?????using?System.Text;????namespace?test{????class?QuickSort????{????????static?void?Main(string[]?args)????????{????????????int[]?array?=?{?49,?38,?65,?97,?76,?13,?27?};????????????sort(array,?0,?array.Length?-?1);????????????Console.ReadLine();????????}????????/**一次排序單元，完成此方法，key左邊都比key小，key右邊都比key大。?????????**@param?array排序數(shù)組??????????**@param?low排序起始位置??????????**@param?high排序結(jié)束位置?????????**@return單元排序后的數(shù)組?*/????????private?static?int?sortUnit(int[]?array,?int?low,?int?high)????????{????????????int?key?=?array[low];????????????while?(low?<?high)????????????{????????????????/*從后向前搜索比key小的值*/????????????????while?(array[high]?>=?key?&&?high?>?low)????????????????????--high;?????????????????/*比key小的放左邊*/????????????????array[low]?=?array[high];???????????????????/*從前向后搜索比key大的值，比key大的放右邊*/????????????????while?(array[low]?<=?key?&&?high?>?low)????????????????????++low;?????????????????/*比key大的放右邊*/????????????????array[high]?=?array[low];????????????}????????????/*左邊都比key小，右邊都比key大。//將key放在游標(biāo)當(dāng)前位置。//此時(shí)low等于high?*/????????????array[low]?=?key;????????????foreach?(int?i?in?array)????????????{????????????????Console.Write("{0}\t",?i);????????????}????????????Console.WriteLine();????????????return?high;????????}????????????/**快速排序?*@paramarry?*@return?*/????????public?static?void?sort(int[]?array,?int?low,?int?high)????????{????????????if?(low?>=?high)????????????????return;?????????????/*完成一次單元排序*/????????????int?index?=?sortUnit(array,?low,?high);?????????????/*對(duì)左邊單元進(jìn)行排序*/????????????sort(array,?low,?index?-?1);????????????/*對(duì)右邊單元進(jìn)行排序*/????????????sort(array,?index?+?1,?high);????????}????}}?

運(yùn)行結(jié)果：27 38 13 49 76 97 65

13 27 38 49 76 97 65

13 27 38 49 65 76 97

快速排序就是遞歸調(diào)用此過(guò)程——在以49為中點(diǎn)分割這個(gè)數(shù)據(jù)序列，分別對(duì)前面一部分和后面一部分進(jìn)行類似的快速排序，從而完成全部數(shù)據(jù)序列的快速排序，最后把此數(shù)據(jù)序列變成一個(gè)有序的序列，根據(jù)這種思想對(duì)于上述數(shù)組A的快速排序的全過(guò)程如圖6所示：

初始狀態(tài) {49 38 65 97 76 13 27} 進(jìn)行一次快速排序之后劃分為 {27 38 13} 49 {76 97 65} 分別對(duì)前后兩部分進(jìn)行快速排序{27 38 13} 經(jīng)第三步和第四步交換后變成 {13 27 38} 完成排序。{76 97 65} 經(jīng)第三步和第四步交換后變成 {65 76 97} 完成排序。圖示

F#

<pre data-lang="scala">let?rec?qsort?=?????function????[]?->?[]????|x::xs?->????????qsort?[for?i?in?xs?do?if?i?<?x?then?yield?i]@????????x::qsort?[for?i?in?xs?do?if?i?>=?x?then?yield?i]

PHP

<pre data-lang="php"><?php$arr?=?array(25,133,452,364,5876,293,607,365,8745,534,18,33);function?quick_sort($arr){????//?判斷是否需要繼續(xù)????if?(count($arr)?<=?1)?{????????return?$arr;????}????$middle?=?$arr[0];?//?中間值????$left?=?array();?//?小于中間值????$right?=?array();//?大于中間值????//?循環(huán)比較????for?($i=1;?$i?<?count($arr);?$i++)?{?????????if?($middle?<?$arr[$i])?{????????????//?大于中間值????????????$right[]?=?$arr[$i];????????}?else?{????????????//?小于中間值????????????$left[]?=?$arr[$i];????????}????}????//?遞歸排序兩邊????$left?=?quick_sort($left);????$right?=?quick_sort($right);????//?合并排序后的數(shù)據(jù)，別忘了合并中間值????return?array_merge($left,?array($middle),?$right);}var_dump($arr);var_dump(quick_sort($arr));

Pascal

<pre data-lang="delphi">這里是完全程序，過(guò)程部分為快排program?qsort;var?n,p:integer;????a:array[0..100000]?of?integer;procedure?qs(l,r:integer);//假設(shè)被排序的數(shù)組是a,且快排后按升序排列）var?i,j,m,t:integer;begin??i:=l;??j:=r;//(l（left）,r（right）表示快排的左右區(qū)間)??m:=a[(l+r)div2];//注意：本句不能寫(xiě)成：m:=(l+r)div2;??repeat??while?a[i]<m?do?inc(i);??while?a[j]>m?do?dec(j);//若是降序把'<'與‘>'互換;??if?i<=j?then????begin????t:=a[i];????a[i]:=a[j];????a[j]:=t;????inc(i);????dec(j);????end;??until?i>j;??if?l<j?then?qs(l,j);//遞歸查找左區(qū)間??if?i<r?then?qs(i,r);//遞歸查找右區(qū)間end;begin??readln(n);//有n個(gè)數(shù)據(jù)要處理??for?p:=1?to?n?do?read(a[p]);//輸入數(shù)據(jù)??qs(1,n);??for?p:=1?to?n?do?write(a[p],'');//輸出快排后的數(shù)據(jù)end.或者procedure?quickSort(var?a:array?of?integer;l,r:Integer);var?i,j,x:integer;begin??if?l>=r?then?exit;??i:=l;??j:=r;??x:=a[i];??while?i<=j?do?????begin????while?(i<j)and(a[j]>x)?do?dec(j);????if?i<j?then???????begin??????a[i]:=a[j];??????inc(i);??????end;????while?(i<j)and(a[i]<x)?do?inc(i);????if?i<j?then???????begin??????a[j]:=a[i];??????dec(j);??????end;????a[i]:=x;????quicksort(a,l,i-1);????quicksort(a,i+1,r);????end;end;

Python3：分而治之+遞歸

<pre data-lang="ruby">def?quick_sort(data):????????"""快速排序"""????????if?len(data)?>=?2:??#?遞歸入口及出口????????????????mid?=?data[len(data)//2]??#?選取基準(zhǔn)值，也可以選取第一個(gè)或最后一個(gè)元素????????????????left,?right?=?[],?[]??#?定義基準(zhǔn)值左右兩側(cè)的列表????????????????data.remove(mid)??#?從原始數(shù)組中移除基準(zhǔn)值????????????????for?num?in?data:????????????????????????if?num?>=?mid:????????????????????????????????right.append(num)????????????????????????else:????????????????????????????????left.append(num)????????????????return?quick_sort(left)?+?[mid]?+?quick_sort(right)????????else:????????????????return?data#?示例：array?=?[2,3,5,7,1,4,6,15,5,2,7,9,10,15,9,17,12]print(quick_sort(array))#?輸出為[1,?2,?2,?3,?4,?5,?5,?6,?7,?7,?9,?9,?10,?12,?15,?15,?17]

Rust

<pre data-lang="clike">fn quick_sort<T: PartialOrd + Copy>(list: &mut Vec<T>) -> &mut Vec<T> { if list.len() > 1 {  //獲取隨機(jī)基準(zhǔn)值  let elme = list[rand::thread_rng().gen_range(1, list.len())];  let (mut left, mut right) = (Vec::new(), Vec::new());  //根據(jù)基準(zhǔn)值比較,排序后的值放在左邊還是右邊  for num in list.iter_mut() {   if *num == elme {    continue;   } else if *num < elme {    left.push(*num);   } else {    right.push(*num);   }  }  //遞歸調(diào)用分治  let (mut left, mut right) = (quick_sort(&mut left), quick_sort(&mut right));  left.push(elme);  left.append(&mut right);  //由于無(wú)法返回不同的聲明周期的Vec，轉(zhuǎn)而求其次，重新賦值  list.truncate(0); //清理  list.append(&mut left); //裝彈 } list}#?示例：use rand::Rng;fn main() { let mut list = vec![3, 5, 8, 1, 2, 9, 4, 7, 6]; quick_sort(&mut list); assert_eq!(list, [1, 2, 3, 4, 5, 6, 7, 8, 9]);}

性能分析

快速排序的一次劃分算法從兩頭交替搜索，直到low和hight重合，因此其時(shí)間復(fù)雜度是O(n)；而整個(gè)快速排序算法的時(shí)間復(fù)雜度與劃分的趟數(shù)有關(guān)。4

理想的情況是，每次劃分所選擇的中間數(shù)恰好將當(dāng)前序列幾乎等分，經(jīng)過(guò)log2n趟劃分，便可得到長(zhǎng)度為1的子表。這樣，整個(gè)算法的時(shí)間復(fù)雜度為O(nlog2n)。4

最壞的情況是，每次所選的中間數(shù)是當(dāng)前序列中的最大或最小元素，這使得每次劃分所得的子表中一個(gè)為空表，另一子表的長(zhǎng)度為原表的長(zhǎng)度-1。這樣，長(zhǎng)度為n的數(shù)據(jù)表的快速排序需要經(jīng)過(guò)n趟劃分，使得整個(gè)排序算法的時(shí)間復(fù)雜度為O(n2)。4

為改善最壞情況下的時(shí)間性能，可采用其他方法選取中間數(shù)。通常采用“三者值取中”方法，即比較H->r[low].key、H->r[high].key與H->r[(low+high)/2].key，取三者中關(guān)鍵字為中值的元素為中間數(shù)。4

可以證明，快速排序的平均時(shí)間復(fù)雜度也是O(nlog2n)。因此，該排序方法被認(rèn)為是目前最好的一種內(nèi)部排序方法。4

從空間性能上看，盡管快速排序只需要一個(gè)元素的輔助空間，但快速排序需要一個(gè)?？臻g來(lái)實(shí)現(xiàn)遞歸。最好的情況下，即快速排序的每一趟排序都將元素序列均勻地分割成長(zhǎng)度相近的兩個(gè)子表，所需棧的最大深度為log2(n+1)；但最壞的情況下，棧的最大深度為n。這樣，快速排序的空間復(fù)雜度為O(log2n)。4