快速排序算法

快速排序（Quicksort）是對冒泡排序的一種改進。

快速排序由C. A. R. Hoare在1960年提出。它的基本思想是：通過一趟排序將要排序的數據分割成獨立的兩部分，其中一部分的所有數據都比另外一部分的所有數據都要小，然後再按此方法對這兩部分數據分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數據變成有序序列。

基本介紹

• 中文名：快速排序算法
• 外文名：quick sort
• 別稱：快速排序
• 提出者：C. A. R. Hoare
• 提出時間：1960年
• 套用學科：計算機科學
• 適用領域範圍：Pascal，c++等語言

排序流程

快速排序算法通過多次比較和交換來實現排序，其排序流程如下：

(1)首先設定一個分界值，通過該分界值將數組分成左右兩部分。

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

(3)然後，左邊和右邊的數據可以獨立排序。對於左側的數組數據，又可以取一個分界值，將該部分數據分成左右兩部分，同樣在左邊放置較小值，右邊放置較大值。右側的數組數據也可以做類似處理。

(4)重複上述過程，可以看出，這是一個遞歸定義。通過遞歸將左側部分排好序後，再遞歸排好右側部分的順序。當左、右兩個部分各數據排序完成後，整個數組的排序也就完成了。

排序步驟

原理

設要排序的數組是A[0]……A[N-1]，首先任意選取一個數據（通常選

快排圖

用數組的第一個數）作為關鍵數據，然後將所有比它小的數都放到它左邊，所有比它大的數都放到它右邊，這個過程稱為一趟快速排序。值得注意的是，快速排序不是一種穩定的排序算法，也就是說，多個相同的值的相對位置也許會在算法結束時產生變動。

一趟快速排序的算法是：

1）設定兩個變數i、j，排序開始的時候：i=0，j=N-1；

2）以第一個數組元素作為關鍵數據，賦值給key，即key=A[0]；

3）從j開始向前搜尋，即由後開始向前搜尋(j--)，找到第一個小於key的值A[j]，將A[j]和A[i]的值交換；

4）從i開始向後搜尋，即由前開始向後搜尋(i++)，找到第一個大於key的A[i]，將A[i]和A[j]的值交換；

5）重複第3、4步，直到i=j； (3,4步中，沒找到符合條件的值，即3中A[j]不小於key,4中A[i]不大於key的時候改變j、i的值，使得j=j-1，i=i+1，直至找到為止。找到符合條件的值，進行交換的時候i， j指針位置不變。另外，i==j這一過程一定正好是i+或j-完成的時候，此時令循環結束）。

排序演示

假設一開始序列{x_i}是：5，3，7，6，4，1，0，2，9，10，8。

此時，ref=5，i=1，j=11，從後往前找，第一個比5小的數是x₈=2，因此序列為：2，3，7，6，4，1，0，5，9，10，8。此時i=1，j=8，從前往後找，第一個比5大的數是x₃=7，因此序列為：2，3，5，6，4，1，0，7，9，10，8。此時，i=3，j=8，從第8位往前找，第一個比5小的數是x₇=0，因此：2，3，0，6，4，1，5，7，9，10，8。此時，i=3，j=7，從第3位往後找，第一個比5大的數是x₄=6，因此：2，3，0，5，4，1，6，7，9，10，8。此時，i=4，j=7，從第7位往前找，第一個比5小的數是x₆=1，因此：2，3，0，1，4，5，6，7，9，10，8。此時，i=4，j=6，從第4位往後找，直到第6位才有比5大的數，這時，i=j=6，ref成為一條分界線，它之前的數都比它小，之後的數都比它大，對於前後兩部分數，可以採用同樣的方法來排序。

程式調用舉例

用法:

void qsort(void *base, int nelem, int width, int (*fcmp)(const void *,const void *));

參數：
1、待排序數組首地址；

2、數組中待排序元素數量；

3、各元素的占用空間大小；

4、指向函式的指針，用於確定排序的順序。

示例代碼

GO

// 第一種寫法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)}// 第二種寫法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:])}// 第三種寫法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

def quick_sort(a)    (x=a.pop) ? quick_sort(a.select { |i| i <= x }) + [x] + quick_sort(a.select { |i| i > x }) : []end

Erlang語言

超簡短實現：q_sort([])->[];q_sort([H|R])->q_sort([X||X<-R,X<H])++[H]++q_sort([X||X<-R,X>=H]).

Haskell語言

q_sort n=case n of    []->[]    (x:xs)->q_sort [a|a<-xs,a<=x]++[x]++q_sort [a|a<-xs,a>x]

C++語言

#include <iostream>using namespace std;void Qsort(int arr[], int low, int high){    if (high <= low) return;    int i = low;    int j = high + 1;    int key = arr[low];    while (true)    {        /*從左向右找比key大的值*/        while (arr[++i] < key)        {            if (i == high){                break;            }        }        /*從右向左找比key小的值*/        while (arr[--j] > key)        {            if (j == low){                break;            }        }        if (i >= j) break;        /*交換i,j對應的值*/        int temp = arr[i];        arr[i] = arr[j];        arr[j] = temp;    }    /*中樞值與j對應值交換*/    int temp = arr[low];    arr[low] = arr[j];    arr[j] = temp;    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);/*這裡原文第三個參數要減1否則記憶體越界*/    for(int i = 0; i < sizeof(a) / sizeof(a[0]); i++)    {        cout << a[i] << "";    }        return 0;}/*參考數據結構p274(清華大學出版社，嚴蔚敏)*/

C語言版本

void sort(int *a, int left, int right){    if(left >= right)/*如果左邊索引大於或者等於右邊的索引就代表已經整理完成一個組了*/    {        return ;    }    int i = left;    int j = right;    int key = a[left];        while(i < j)                               /*控制在當組內尋找一遍*/    {        while(i < j && key <= a[j])        /*而尋找結束的條件就是，1，找到一個小於或者大於key的數（大於或小於取決於你想升        序還是降序）2，沒有符合條件1的，並且i與j的大小沒有反轉*/         {            j--;/*向前尋找*/        }                a[i] = a[j];        /*找到一個這樣的數後就把它賦給前面的被拿走的i的值（如果第一次循環且key是        a[left]，那么就是給key）*/                while(i < j && key >= a[i])        /*這是i在當組內向前尋找，同上，不過注意與key的大小關係停止循環和上面相反，        因為排序思想是把數往兩邊扔，所以左右兩邊的數大小與key的關係相反*/        {            i++;        }                a[j] = a[i];    }        a[i] = key;/*當在當組內找完一遍以後就把中間數key回歸*/    sort(a, left, i - 1);/*最後用同樣的方式對分出來的左邊的小組進行同上的做法*/    sort(a, i + 1, right);/*用同樣的方式對分出來的右邊的小組進行同上的做法*/                       /*當然最後可能會出現很多分左右，直到每一組的i = j 為止*/}

Swift

func quickSort(a: inout [Int], low: Int, high: Int) {    if low >= high { // 遞歸結束條件        return    }    var i = low    var j = high    let key = a[i]    while i < j {        // 從右邊開始比較，比key大的數位置不變        while i < j && a[j] >= key {            j -= 1        }        // 只要出現一個比key小的數，將這個數放入左邊i的位置        a[i] = a[j]        // 從左邊開始比較，比key小的數位置不變        while i < j && a[i] <= key {            i += 1        }        // 只要出現一個比key大的數，將這個數放入右邊j的位置        a[j] = a[i]    }    a[i] = key // 將key放入i的位置，則左側數都比key小，右側數都比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)// 結果：[1, 2, 2, 3, 4, 5, 5, 6, 7, 7, 9, 9, 10, 12, 15, 15, 17]

Objective-C

+ (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) { // 當key是目前最小的數時，會出現i=j的情況，            break;        }        m[i++] = m[j]; // i++ 會減少一次m[i]和key的比較        while (i < j && [m[i] intValue] <= [key intValue]) {            i++;        }          if (i == j) { // 當key是目前最大的數時(m[j]的前面)，會出現i=j的情況            break;        }        m[j--] = m[i]; //j-- 會減少一次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

const quickSort = (array) => { const sort = (arr, left = 0, right = arr.length - 1) => {  if (left >= right) {//如果左邊的索引大於等於右邊的索引說明整理完畢   return  } let i = left let j = right const baseVal = arr[j] // 取無序數組最後一個數為基準值 while (i < j) {//把所有比基準值小的數放在左邊大的數放在右邊  while (i < j && arr[i] <= baseVal) { //找到一個比基準值大的數交換   i++  }  arr[j] = arr[i] // 將較大的值放在右邊如果沒有比基準值大的數就是將自己賦值給自己（i 等於 j）  while (j > i && arr[j] >= baseVal) { //找到一個比基準值小的數交換   j-- }  arr[i] = arr[j] // 將較小的值放在左邊如果沒有找到比基準值小的數就是將自己賦值給自己（i 等於 j） } arr[j] = baseVal // 將基準值放至中央位置完成一次循環（這時候 j 等於 i ） sort(arr, left, j-1) // 將左邊的無序數組重複上面的操作 sort(arr, j+1, right) // 將右邊的無序數組重複上面的操作 } const newArr = array.concat() // 為了保證這個函式是純函式拷貝一次數組 sort(newArr) return newArr}

Java

public static int[] qsort(int arr[],int start,int end) {            int pivot = arr[start];            int i = start;            int j = end;            while (i<j) {                    while ((i<j)&&(arr[j]>pivot)) {                            j--;                    }                    while ((i<j)&&(arr[i]<pivot)) {                            i++;                    }                    if ((arr[i]==arr[j])&&(i<j)) {                            i++;                    } else {                            int temp = arr[i];                            arr[i] = arr[j];                            arr[j] = temp;                    }            }            if (i-1>start) arr=qsort(arr,start,i-1);            if (j+1<end) arr=qsort(arr,j+1,end);            return (arr);    }    public static void main(String[] args) {            int arr[] = new int[]{3,3,3,7,9,122344,4656,34,34,4656,5,6,7,8,9,343,57765,23,12321};            int len = arr.length-1;            arr=qsort(arr,0,len);            for (int i:arr) {                    System.out.print(i+"\t");            }    }/*//////////////////////////方式二////////////////////////////////*/更高效點的代碼：(TextendsComparable和SortUtil都是自己封裝的類，裡面重寫和實現了compareTo和swap方法)public <TextendsComparable<?superT>>T[] quickSort(T[] targetArr,int start,int end){inti=start+1,j=end;T key=targetArr[start];SortUtil<T> sUtil=new SortUtil<T>();if(start==end)return(targetArr);/*從i++和j--兩個方向搜尋不滿足條件的值並交換**條件為：i++方向小於key，j--方向大於key*/while(true){while(targetArr[j].compareTo(key)>0)j--;while(targetArr[i].compareTo(key)<0&&i<j)i++;if(i>=j)break;sUtil.swap(targetArr,i,j);if(targetArr[i]==key){j--;}else{i++;}}/*關鍵數據放到‘中間’*/sUtil.swap(targetArr,start,j);if(start<i-1){this.quickSort(targetArr,start,i-1);}if(j+1<end){this.quickSort(targetArr,j+1,end);}returntargetArr;}/*//////////////方式三：減少交換次數，提高效率/////////////////////*/private<TextendsComparable<?superT>>voidquickSort(T[]targetArr,intstart,intend){inti=start,j=end;Tkey=targetArr[start];while(i<j){/*按j--方向遍歷目標數組，直到比key小的值為止*/while(j>i&&targetArr[j].compareTo(key)>=0){j--;}if(i<j){/*targetArr[i]已經保存在key中，可將後面的數填入*/targetArr[i]=targetArr[j];i++;}/*按i++方向遍歷目標數組，直到比key大的值為止*/while(i<j&&targetArr[i].compareTo(key)<=0)/*此處一定要小於等於零，假設數組之內有一億個1，0交替出現的話，而key的值又恰巧是1的話，那么這個小於等於的作用就會使下面的if語句少執行一億次。*/{i++;}if(i<j){/*targetArr[j]已保存在targetArr[i]中，可將前面的值填入*/targetArr[j]=targetArr[i];j--;}}/*此時i==j*/targetArr[i]=key;//應加判斷/*遞歸調用，把key前面的完成排序*/this.quickSort(targetArr,start,i-1);/*遞歸調用，把key後面的完成排序*/this.quickSort(targetArr,j+1,end);//兩個遞歸應加判斷}

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排序數組          **@param low排序起始位置          **@param high排序結束位置         **@return單元排序後的數組 */        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放在游標當前位置。//此時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);             /*對左邊單元進行排序*/            sort(array, low, index - 1);            /*對右邊單元進行排序*/            sort(array, index + 1, high);        }    }} 

運行結果：27 38 13 49 76 97 65

13 27 38 49 76 97 65
13 27 38 49 65 76 97

快速排序就是遞歸調用此過程——在以49為中點分割這個數據序列，分別對前面一部分和後面一部分進行類似的快速排序，從而完成全部數據序列的快速排序，最後把此數據序列變成一個有序的序列，根據這種思想對於上述數組A的快速排序的全過程如圖6所示：

初始狀態 {49 38 65 97 76 13 27} 進行一次快速排序之後劃分為 {27 38 13} 49 {76 97 65} 分別對前後兩部分進行快速排序{27 38 13} 經第三步和第四步交換後變成 {13 27 38} 完成排序。{76 97 65} 經第三步和第四步交換後變成 {65 76 97} 完成排序。圖示

F#

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

<?php$arr = array(25,133,452,364,5876,293,607,365,8745,534,18,33);function quick_sort($arr){    // 判斷是否需要繼續    if (count($arr) <= 1) {        return $arr;    }    $middle = $arr[0]; // 中間值    $left = array(); // 小於中間值    $right = array();// 大於中間值    // 循環比較    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);    // 合併排序後的數據，別忘了合併中間值    return array_merge($left, array($middle), $right);}var_dump($arr);var_dump(quick_sort($arr));

Pascal

這裡是完全程式，過程部分為快排program qsort;var n,p:integer;    a:array[0..100000] of integer;procedure qs(l,r:integer);//假設被排序的數組是a,且快排後按升序排列）var i,j,m,t:integer;begin  i:=l;  j:=r;//(l（left）,r（right）表示快排的左右區間)  m:=a[(l+r)div2];//注意：本句不能寫成：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);//遞歸查找左區間  if i<r then qs(i,r);//遞歸查找右區間end;begin  readln(n);//有n個數據要處理  for p:=1 to n do read(a[p]);//輸入數據  qs(1,n);  for p:=1 to n do write(a[p],'');//輸出快排後的數據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：分而治之+遞歸

def quick_sort(data):        """快速排序"""        if len(data) >= 2:  # 遞歸入口及出口                mid = data[len(data)//2]  # 選取基準值，也可以選取第一個或最後一個元素                left, right = [], []  # 定義基準值左右兩側的列表                data.remove(mid)  # 從原始數組中移除基準值                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]

性能分析

快速排序的一次劃分算法從兩頭交替搜尋，直到low和high重合，因此其時間複雜度是O(n)；而整個快速排序算法的時間複雜度與劃分的趟數有關。

理想的情況是，每次劃分所選擇的中間數恰好將當前序列幾乎等分，經過log₂n趟劃分，便可得到長度為1的子表。這樣，整個算法的時間複雜度為O(nlog₂n)。

最壞的情況是，每次所選的中間數是當前序列中的最大或最小元素，這使得每次劃分所得的子表中一個為空表，另一子表的長度為原表的長度-1。這樣，長度為n的數據表的快速排序需要經過n趟劃分，使得整個排序算法的時間複雜度為O(n²)。

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

可以證明，快速排序的平均時間複雜度也是O(nlog₂n)。因此，該排序方法被認為是目前最好的一種內部排序方法。

從空間性能上看，儘管快速排序只需要一個元素的輔助空間，但快速排序需要一個棧空間來實現遞歸。最好的情況下，即快速排序的每一趟排序都將元素序列均勻地分割成長度相近的兩個子表，所需棧的最大深度為log₂(n+1)；但最壞的情況下，棧的最大深度為n。這樣，快速排序的空間複雜度為O(log₂n))。