.example-btn{color:#fff;background-color:#5cb85c;border-color:#4cae4c}.example-btn:hover{color:#fff;background-color:#47a447;border-color:#398439}.example-btn:active{background-image:none}div.example{width:98%;color:#000;background-color:#f6f4f0;background-color:#d0e69c;background-color:#dcecb5;background-color:#e5eecc;margin:0 0 5px 0;padding:5px;border:1px solid #d4d4d4;background-image:-webkit-linear-gradient(#fff,#e5eecc 100px);background-image:linear-gradient(#fff,#e5eecc 100px)}div.example_code{line-height:1.4em;width:98%;background-color:#fff;padding:5px;border:1px solid #d4d4d4;font-size:110%;font-family:Menlo,Monaco,Consolas,"Andale Mono","lucida console","Courier New",monospace;word-break:break-all;word-wrap:break-word}div.example_result{background-color:#fff;padding:4px;border:1px solid #d4d4d4;width:98%}div.code{width:98%;border:1px solid #d4d4d4;background-color:#f6f4f0;color:#444;padding:5px;margin:0}div.code div{font-size:110%}div.code div,div.code p,div.example_code p{font-family:"courier new"}pre{margin:15px auto;font:12px/20px Menlo,Monaco,Consolas,"Andale Mono","lucida console","Courier New",monospace;white-space:pre-wrap;word-break:break-all;word-wrap:break-word;border:1px solid #ddd;border-left-width:4px;padding:10px 15px}

排序算法是《數據結構與算法》中最基本的算法之一。排序算法可以分為內部排序和外部排序，內部排序是數據記錄在內存中進行排序，而外部排序是因排序的數據很大，一次不能容納全部的排序記錄，在排序過程中需要訪問外存。常見的內部排序算法有：插入排序、希爾排序、選擇排序、冒泡排序、歸并排序、快速排序、堆排序、基數排序等。以下是快速排序算法：

快速排序是由東尼·霍爾所發(fā)展的一種排序算法。在平均狀況下，排序 n 個項目要 Ο(nlogn) 次比較。在最壞狀況下則需要 Ο(n2) 次比較，但這種狀況并不常見。事實上，快速排序通常明顯比其他 Ο(nlogn) 算法更快，因為它的內部循環(huán)（inner loop）可以在大部分的架構上很有效率地被實現出來。

快速排序使用分治法（Divide and conquer）策略來把一個串行（list）分為兩個子串行（sub-lists）。

快速排序又是一種分而治之思想在排序算法上的典型應用。本質上來看，快速排序應該算是在冒泡排序基礎上的遞歸分治法。

快速排序的名字起的是簡單粗暴，因為一聽到這個名字你就知道它存在的意義，就是快，而且效率高！它是處理大數據最快的排序算法之一了。雖然 Worst Case 的時間復雜度達到了 O(n?)，但是人家就是優(yōu)秀，在大多數情況下都比平均時間復雜度為 O(n logn) 的排序算法表現要更好，可是這是為什么呢，我也不知道。好在我的強迫癥又犯了，查了 N 多資料終于在《算法藝術與信息學競賽》上找到了滿意的答案：

快速排序的最壞運行情況是 O(n?)，比如說順序數列的快排。但它的平攤期望時間是 O(nlogn)，且 O(nlogn) 記號中隱含的常數因子很小，比復雜度穩(wěn)定等于 O(nlogn) 的歸并排序要小很多。所以，對絕大多數順序性較弱的隨機數列而言，快速排序總是優(yōu)于歸并排序。

1. 算法步驟

從數列中挑出一個元素，稱為 "基準"（pivot）;

重新排序數列，所有元素比基準值小的擺放在基準前面，所有元素比基準值大的擺在基準的后面（相同的數可以到任一邊）。在這個分區(qū)退出之后，該基準就處于數列的中間位置。這個稱為分區(qū)（partition）操作；

遞歸地（recursive）把小于基準值元素的子數列和大于基準值元素的子數列排序；

2. 動圖演示

代碼實現JavaScript實例 function quickSort(arr, left, right) {? ? var len = arr.length,? ? ? ? partitionIndex,? ? ? ? left = typeof left != 'number' ? 0 : left,? ? ? ? right = typeof right != 'number' ? len - 1 : right;? ? if (left < right) {? ? ? ? partitionIndex = partition(arr, left, right);? ? ? ? quickSort(arr, left, partitionIndex-1);? ? ? ? quickSort(arr, partitionIndex+1, right);? ? }? ? return arr;}function partition(arr, left ,right) { ? ? // 分區(qū)操作? ? var pivot = left, ? ? ? ? ? ? ? ? ? ? ?// 設定基準值（pivot）? ? ? ? index = pivot + 1;? ? for (var i = index; i <= right; i++) {? ? ? ? if (arr[i] < arr[pivot]) {? ? ? ? ? ? swap(arr, i, index);? ? ? ? ? ? index++;? ? ? ? } ? ? ? ?? ? }? ? swap(arr, pivot, index - 1);? ? return index-1;}function swap(arr, i, j) {? ? var temp = arr[i];? ? arr[i] = arr[j];? ? arr[j] = temp;}function partition2(arr, low, high) {? let pivot = arr[low];? while (low < high) {? ? while (low < high && arr[high] > pivot) {? ? ? --high;? ? }? ? arr[low] = arr[high];? ? while (low < high && arr[low] <= pivot) {? ? ? ++low;? ? }? ? arr[high] = arr[low];? }? arr[low] = pivot;? return low;}function quickSort2(arr, low, high) {? if (low < high) {? ? let pivot = partition2(arr, low, high);? ? quickSort2(arr, low, pivot - 1);? ? quickSort2(arr, pivot + 1, high);? }? return arr;}Python實例 def quickSort(arr, left=None, right=None):? ? left = 0 if not isinstance(left,(int, float)) else left? ? right = len(arr)-1 if not isinstance(right,(int, float)) else right? ? if left < right:? ? ? ? partitionIndex = partition(arr, left, right)? ? ? ? quickSort(arr, left, partitionIndex-1)? ? ? ? quickSort(arr, partitionIndex+1, right)? ? return arrdef partition(arr, left, right):? ? pivot = left? ? index = pivot+1? ? i = index? ? while ?i <= right:? ? ? ? if arr[i] < arr[pivot]:? ? ? ? ? ? swap(arr, i, index)? ? ? ? ? ? index+=1? ? ? ? i+=1? ? swap(arr,pivot,index-1)? ? return index-1def swap(arr, i, j):? ? arr[i], arr[j] = arr[j], arr[i]Go實例 func quickSort(arr []int) []int {? ? ? ? return _quickSort(arr, 0, len(arr)-1)}func _quickSort(arr []int, left, right int) []int {? ? ? ? if left < right {? ? ? ? ? ? ? ? partitionIndex := partition(arr, left, right)? ? ? ? ? ? ? ? _quickSort(arr, left, partitionIndex-1)? ? ? ? ? ? ? ? _quickSort(arr, partitionIndex+1, right)? ? ? ? }? ? ? ? return arr}func partition(arr []int, left, right int) int {? ? ? ? pivot := left? ? ? ? index := pivot + 1? ? ? ? for i := index; i <= right; i++ {? ? ? ? ? ? ? ? if arr[i] < arr[pivot] {? ? ? ? ? ? ? ? ? ? ? ? swap(arr, i, index)? ? ? ? ? ? ? ? ? ? ? ? index += 1? ? ? ? ? ? ? ? }? ? ? ? }? ? ? ? swap(arr, pivot, index-1)? ? ? ? return index - 1}func swap(arr []int, i, j int) {? ? ? ? arr[i], arr[j] = arr[j], arr[i]}C++ 實例 //嚴蔚敏《數據結構》標準分割函數?Paritition1(int A[], int low, int high) {? ?int pivot = A[low];? ?while (low < high) {? ? ?while (low < high && A[high] >= pivot) {? ? ? ?--high;? ? ?}? ? ?A[low] = A[high];? ? ?while (low < high && A[low] <= pivot) {? ? ? ?++low;? ? ?}? ? ?A[high] = A[low];? ?}? ?A[low] = pivot;? ?return low;?}?void QuickSort(int A[], int low, int high) //快排母函數?{? ?if (low < high) {? ? ?int pivot = Paritition1(A, low, high);? ? ?QuickSort(A, low, pivot - 1);? ? ?QuickSort(A, pivot + 1, high);? ?}?}Java實例 public class QuickSort implements IArraySort {? ? @Override? ? public int[] sort(int[] sourceArray) throws Exception {? ? ? ? // 對 arr 進行拷貝，不改變參數內容? ? ? ? int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);? ? ? ? return quickSort(arr, 0, arr.length - 1);? ? }? ? private int[] quickSort(int[] arr, int left, int right) {? ? ? ? if (left < right) {? ? ? ? ? ? int partitionIndex = partition(arr, left, right);? ? ? ? ? ? quickSort(arr, left, partitionIndex - 1);? ? ? ? ? ? quickSort(arr, partitionIndex + 1, right);? ? ? ? }? ? ? ? return arr;? ? }? ? private int partition(int[] arr, int left, int right) {? ? ? ? // 設定基準值（pivot）? ? ? ? int pivot = left;? ? ? ? int index = pivot + 1;? ? ? ? for (int i = index; i <= right; i++) {? ? ? ? ? ? if (arr[i] < arr[pivot]) {? ? ? ? ? ? ? ? swap(arr, i, index);? ? ? ? ? ? ? ? index++;? ? ? ? ? ? }? ? ? ? }? ? ? ? swap(arr, pivot, index - 1);? ? ? ? return index - 1;? ? }? ? private void swap(int[] arr, int i, int j) {? ? ? ? int temp = arr[i];? ? ? ? arr[i] = arr[j];? ? ? ? arr[j] = temp;? ? }}PHP實例 function quickSort($arr){? ? if (count($arr) <= 1)? ? ? ? return $arr;? ? $middle = $arr[0];? ? $leftArray = array();? ? $rightArray = array();? ? for ($i = 1; $i < count($arr); $i++) {? ? ? ? if ($arr[$i] > $middle)? ? ? ? ? ? $rightArray[] = $arr[$i];? ? ? ? else? ? ? ? ? ? $leftArray[] = $arr[$i];? ? }? ? $leftArray = quickSort($leftArray);? ? $leftArray[] = $middle;? ? $rightArray = quickSort($rightArray);? ? return array_merge($leftArray, $rightArray);}C實例 typedef struct _Range {? ? int start, end;} Range;Range new_Range(int s, int e) {? ? Range r;? ? r.start = s;? ? r.end = e;? ? return r;}void swap(int *x, int *y) {? ? int t = *x;? ? *x = *y;? ? *y = t;}void quick_sort(int arr[], const int len) {? ? if (len <= 0)? ? ? ? return; // 避免len等於負值時引發(fā)段錯誤（Segment Fault）? ? // r[]模擬列表,p為數量,r[p++]為push,r[--p]為pop且取得元素? ? Range r[len];? ? int p = 0;? ? r[p++] = new_Range(0, len - 1);? ? while (p) {? ? ? ? Range range = r[--p];? ? ? ? if (range.start >= range.end)? ? ? ? ? ? continue;? ? ? ? int mid = arr[(range.start + range.end) / 2]; // 選取中間點為基準點? ? ? ? int left = range.start, right = range.end;? ? ? ? do {? ? ? ? ? ? while (arr[left] < mid) ++left; ? // 檢測基準點左側是否符合要求? ? ? ? ? ? while (arr[right] > mid) --right; //檢測基準點右側是否符合要求? ? ? ? ? ? if (left <= right) {? ? ? ? ? ? ? ? swap(&arr[left], &arr[right]);? ? ? ? ? ? ? ? left++;? ? ? ? ? ? ? ? right--; ? ? ? ? ? ? ? // 移動指針以繼續(xù)? ? ? ? ? ? }? ? ? ? } while (left <= right);? ? ? ? if (range.start < right) r[p++] = new_Range(range.start, right);? ? ? ? if (range.end > left) r[p++] = new_Range(left, range.end);? ? }}

遞歸法

實例 void swap(int *x, int *y) {? ? int t = *x;? ? *x = *y;? ? *y = t;}void quick_sort_recursive(int arr[], int start, int end) {? ? if (start >= end)? ? ? ? return;? ? int mid = arr[end];? ? int left = start, right = end - 1;? ? while (left < right) {? ? ? ? while (arr[left] < mid && left < right)? ? ? ? ? ? left++;? ? ? ? while (arr[right] >= mid && left < right)? ? ? ? ? ? right--;? ? ? ? swap(&arr[left], &arr[right]);? ? }? ? if (arr[left] >= arr[end])? ? ? ? swap(&arr[left], &arr[end]);? ? else? ? ? ? left++;? ? if (left)? ? ? ? quick_sort_recursive(arr, start, left - 1);? ? quick_sort_recursive(arr, left + 1, end);}void quick_sort(int arr[], int len) {? ? 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/struct Range {? ? int start, end;? ? Range(int s = 0, int e = 0) {? ? ? ? start = s, end = e;? ? }};template // 整數或浮點數皆可使用,若要使用物件(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++] = Range(0, len - 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);? ? }}

遞歸法

實例 template 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++;? ? ? ? while (arr[right] >= mid && left < right) //試圖在右側找到一個比樞紐元更小的元素? ? ? ? ? ? right--;? ? ? ? std::swap(arr[left], arr[right]); //交換元素? ? }? ? if (arr[left] >= arr[end])? ? ? ? std::swap(arr[left], arr[end]);? ? else? ? ? ? left++;? ? quick_sort_recursive(arr, start, left - 1);? ? quick_sort_recursive(arr, left + 1, end);}template //整數或浮點數皆可使用,若要使用物件(class)時必須設定"小於"(<)、"大於"(>)、"不小於"(>=)的運算子功能void quick_sort(T arr[], int len) {? ? quick_sort_recursive(arr, 0, len - 1);}

參考地址:

https://github.com/hustcc/JS-Sorting-Algorithm/blob/master/6.quickSort.md

https://zh.wikipedia.org/wiki/%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F

以下是熱心網友對快速排序算法的補充，僅供參考：

熱心網友提供的補充1：

上方沒有C#實現，我補充一下，如下所示：

//快速排序（目標數組，數組的起始位置，數組的終止位置）
static void QuickSort(int[] array, int left = 0, int right = -1)
{
    if (right.Equals(-1)) right = array.Length - 1;
    try
    {
        int keyValuePosition;   //記錄關鍵值的下標
        //當傳遞的目標數組含有兩個以上的元素時，進行遞歸調用。（即：當傳遞的目標數組只含有一個元素時，此趟排序結束）
        if (left < right)
        {
            keyValuePosition = Partion(array, left, right);  //獲取關鍵值的下標（快排的核心）
            QuickSort(array, left, keyValuePosition - 1);    //遞歸調用，快排劃分出來的左區(qū)間
            QuickSort(array, keyValuePosition + 1, right);   //遞歸調用，快排劃分出來的右區(qū)間
        }
    }
    catch (Exception ex)
    {
        Console.WriteLine("Exception: {0}", ex);
    }
}

///快速排序的核心部分：確定關鍵值在數組中的位置，以此將數組劃分成左右兩區(qū)間，關鍵值游離在外。（返回關鍵值應在數組中的下標）
static int Partion(int[] array, int left, int right)
{
    int leftIndex = left;        //記錄目標數組的起始位置（后續(xù)動態(tài)的左側下標）
    int rightIndex = right;      //記錄目標數組的結束位置（后續(xù)動態(tài)的右側下標）
    int keyValue = array[left];  //數組的第一個元素作為關鍵值
    int temp;
    //當 （左側動態(tài)下標 == 右側動態(tài)下標） 時跳出循環(huán)
    while (leftIndex < rightIndex)
    {
        while (leftIndex < rightIndex && array[leftIndex] <= keyValue)  //左側動態(tài)下標逐漸增加，直至找到大于keyValue的下標
        {
            leftIndex++;
        }
        while (leftIndex < rightIndex && array[rightIndex] > keyValue)  //右側動態(tài)下標逐漸減小，直至找到小于或等于keyValue的下標
        {
            rightIndex--;
        }
        if (leftIndex < rightIndex)  //如果leftIndex < rightIndex，則交換左右動態(tài)下標所指定的值；當leftIndex==rightIndex時，跳出整個循環(huán)
        {
            temp = array[leftIndex];
            array[leftIndex] = array[rightIndex];
            array[rightIndex] = temp;
        }
    }

    //當左右兩個動態(tài)下標相等時（即：左右下標指向同一個位置），此時便可以確定keyValue的準確位置
    temp = keyValue;
    if (temp < array[rightIndex])   //當keyValue < 左右下標同時指向的值，將keyValue與rightIndex - 1指向的值交換，并返回rightIndex - 1
    {
        array[left] = array[rightIndex - 1];
        array[rightIndex - 1] = temp;
        return rightIndex - 1;
    }
    else //當keyValue >= 左右下標同時指向的值，將keyValue與rightIndex指向的值交換，并返回rightIndex
    {
        array[left] = array[rightIndex];
        array[rightIndex] = temp;
        return rightIndex;
    }
}

熱心網友提供的補充2：

補充 scala 實現版本：

/**  
* @Auther: huowang 
* @Date: 19:34:47 2020/12/10  
* @DES:  分區(qū)交換算法（快速排序發(fā)）  
* @Modified By:  
*/
object PartitionExchange {

  /**    
   * 分區(qū)內切割    
   * @param arr    
   * @param left    
   * @param right    
   * @return    
  */  
def partition(arr:Array[Int],left:Int,right: Int):Int={
    // 獲取基準元素 直接選取最右側一個元素為基準元素   
    val pv=arr(right)

    // 把最左邊一個索引作為堆疊索引   
     var storeIndex=left
    //操作數組 -1是因為 最右邊一個元素是基準元素  
   for (i <- left to right-1 ){
       if(arr(i)<=pv){
         //把小于基準元素的元素 都堆到集合左端        
          swap(arr,storeIndex,i)
         // 把用于堆疊索引往前移動一個  
          storeIndex=storeIndex+1 
      }
      //如果出現了比基準元素大的元素,那么則不會移動堆疊索引  
      // 但是如果之后又出現了比基準元素小的元素,那邊會與這個大的元素交換位置
      // 進而使大的元素永遠出現在堆疊索引右側
    }
    // 這里最有右的元素,其實是基準元素,我們把基準元素和最后堆疊索引對應的元素調換位置
    // 這樣基準元素左邊就都是大于它的元素了  
     swap(arr,right,storeIndex)
    // 返回堆疊索引位置,目前堆疊索引指向的就是基準元素 
     storeIndex
  }

def quicksort(arr:Array[Int],left: Int,right: Int):Array[Int]={

    if(right>left){
      // 左右索引不重合 
     // 隨便選擇一個元素作為基準 就選擇最左邊的吧 
     var pivotIndex=0 
     // 切割返回基準元素 
     pivotIndex= partition(arr,left,right)
      // 遞歸對切割形成的兩個子集進行排序 
      quicksort(arr,left,pivotIndex-1)
      quicksort(arr,pivotIndex,right)
    }
    arr
  }


  /**    
    * 調換 a b 元素在數組中的位置    
    * @param arr    
    * @param a    
    * @param b    
    */  
def swap(arr:Array[Int],a:Int,b:Int)={
    val tmp=arr(a)
    arr(a)=arr(b)
    arr(b)=tmp
  }

def main(args: Array[String]): Unit = {
    // 測試
    val arr=Array(5, 2, 9,11,3,6,8,4,0,0)
    val arrNew=quicksort(arr,0,arr.size-1)
    println(arrNew.toList.mkString(","))

  }
}

熱心網友提供的補充3：

補充一下迭代法的 python 實現：

def _partition(array:list, start:int, end:int) -> int:
    """
    將數組指定片段進行左右劃分，首先選擇中位元素為中值。

    比中位元素小的置于其左，與中位元素相等或比中位元素大的置于其右，

    最后返回中位元素的下標位置。
    """
    # 以中位元素為中值劃分，盡量避免極端情況
    mid = (start + end) >> 1
    array[start], array[mid] = array[mid], array[start]
    
    # 劃分的實現
    i, j = start, end
    x = array[start]
    while (i < j):
        if (i < j and array[j] >= x): j -= 1
        array[i] = array[j]
        if (i < j and array[i] < x): i += 1
        array[j] = array[i]
    array[i] = x

    return i


def quickSort(array:list) -> list:
    """
    迭代法快速排序，隊列結構輔助實現。
    """
    sorted_array = array.copy()
    length = len(sorted_array)
    # 使用隊列保存每次劃分的二元組：(起始下標，終止下標)
    queue = []
    queue.append((0, length - 1))

    # 隊列為空，則所有劃分操作執(zhí)行完畢
    while len(queue):
        left, right = queue.pop(0)
        pos = _partition(sorted_array, left, right)
        # 默認長度為 1 的序列有序，那么區(qū)間長度 > 1 才需要劃分，才需要保存到隊列中
        if (left < pos - 1): queue.append((left, pos - 1))
        if (pos + 1 < right): queue.append((pos + 1, right))
    
    return sorted_array


if __name__ == "__main__":
    array = [21, -17, 1, -27, 41, 17, -5, -49]
    sorted_array = quickSort(array)
    print("排序前：{array1}
排序后：{array2}".format(array1=array, array2=sorted_array))

以上為快速排序算法詳細介紹，插入排序、希爾排序、選擇排序、冒泡排序、歸并排序、快速排序、堆排序、基數排序等排序算法各有優(yōu)缺點，用一張圖概括：

關于時間復雜度

平方階 (O(n2)) 排序 各類簡單排序：直接插入、直接選擇和冒泡排序。

線性對數階 (O(nlog2n)) 排序 快速排序、堆排序和歸并排序；

O(n1+§)) 排序，§ 是介于 0 和 1 之間的常數。 希爾排序

線性階 (O(n)) 排序 基數排序，此外還有桶、箱排序。

關于穩(wěn)定性

穩(wěn)定的排序算法：冒泡排序、插入排序、歸并排序和基數排序。

不是穩(wěn)定的排序算法：選擇排序、快速排序、希爾排序、堆排序。

名詞解釋：

n：數據規(guī)模

k："桶"的個數

In-place：占用常數內存，不占用額外內存

Out-place：占用額外內存

穩(wěn)定性：排序后 2 個相等鍵值的順序和排序之前它們的順序相同