快速排序

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

上面簡單版本的缺點是，它需要的額外儲存空間，也就跟合併排序一樣不好。額外需要的記憶體空間組態，在實際上的實作，也會極度影響速度和快取的效能。有一個比較複雜使用原地（in-place）分割演算法的版本，且在好的基準選擇上，平均可以達到空間的使用複雜度。
 function partition(a, left, right, pivotIndex)
 {
     pivotValue = a[pivotIndex]
     swap(a[pivotIndex], a[right]) // 把pivot移到結尾
     storeIndex = left
     for i from left to right-1
     {
         if a[i] <= pivotValue
          {
             swap(a[storeIndex], a[i])
             storeIndex = storeIndex + 1
          }
     }
     swap(a[right], a[storeIndex]) // 把pivot移到它最後的地方
     return storeIndex
 }
這是原地分割演算法，它分割了標示為"左邊（left）"和"右邊（right）"的序列部份，藉由移動小於a[pivotIndex]的所有元素到子序列的開頭，留下所有大於或等於的元素接在他們後面。在這個過程它也為基準元素找尋最後擺放的位置，也就是它回傳的值。它暫時地把基準元素移到子序列的結尾，而不會被前述方式影響到。由於演算法只使用交換，因此最後的數列與原先的數列擁有一樣的元素。要注意的是，一個元素在到達它的最後位置前，可能會被交換很多次。
一旦我們有了這個分割演算法，要寫快速排列本身就很容易：
 procedure quicksort(a, left, right)
     if right > left
         select a pivot value a[pivotIndex]
         pivotNewIndex := partition(a, left, right, pivotIndex)
         quicksort(a, left, pivotNewIndex-1)
         quicksort(a, pivotNewIndex+1, right)
這個版本經常會被使用在命令式語言中，像是C語言。

最佳化的排序演算法

快速排序是二元搜尋樹（二元搜尋樹）的一個空間最佳化版本。不是循序地把資料項插入到一個明確的樹中，而是由快速排序組織這些資料項到一個由遞迴呼叫所隱含的樹中。這兩個演算法完全地產生相同的比較次數，但是順序不同。對於排序演算法的穩定性指標，原地分割版本的快速排序演算法是不穩定的。其他變種是可以通過犧牲效能和空間來維護穩定性的。
快速排序的最直接競爭者是堆積排序（Heapsort）。堆積排序通常比快速排序稍微慢，但是最壞情況的執行時間總是。快速排序是經常比較快，除了introsort變化版本外，仍然有最壞情況效能的機會。如果事先知道堆積排序將會是需要使用的，那麼直接地使用堆積排序比等待introsort再切換到它還要快。堆積排序也擁有重要的特點，僅使用固定額外的空間（堆積排序是原地排序），而即使是最佳的快速排序變化版本也需要的空間。然而，堆積排序需要有效率的隨機存取才能變成可行。
快速排序也與合併排序（Mergesort）競爭，這是另外一種遞迴排序演算法，但有壞情況執行時間的優勢。不像快速排序或堆積排序，合併排序是一個穩定排序，且可以輕易地被採用在連結串列（linked list）和儲存在慢速存取媒體上像是磁碟儲存或網路連接儲存的非常巨大數列。儘管快速排序可以被重新改寫使用在鏈串列上，但是它通常會因為無法隨機存取而導致差的基準選擇。合併排序的主要缺點，是在最佳情況下需要額外的空間。

正規分析

從一開始快速排序平均需要花費時間的描述並不明顯。但是不難觀察到的是分割運算，陣列的元素都會在每次迴圈中走訪過一次，使用的時間。在使用結合（concatenation）的版本中，這項運算也是。
在最好的情況，每次我們執行一次分割，我們會把一個數列分為兩個幾近相等的片段。這個意思就是每次遞迴呼叫處理一半大小的數列。因此，在到達大小為一的數列前，我們只要作次巢狀的呼叫。這個意思就是呼叫樹的深度是。但是在同一階層的兩個程式呼叫中，不會處理到原來數列的相同部份；因此，程式呼叫的每一階層總共全部僅需要的時間（每個呼叫有某些共同的額外耗費，但是因為在每一階層僅僅只有個呼叫，這些被歸納在係數中）。結果是這個演算法僅需使用時間。
另外一個方法是為設立一個遞迴關係式，也就是需要排序大小為的數列所需要的時間。在最好的情況下，因為一個單獨的快速排序呼叫牽涉了的工作，加上對大小之數列的兩個遞迴呼叫，這個關係式可以是：
解決這種關係式型態的標準數學歸納法技巧告訴我們。
事實上，並不需要把數列如此精確地分割；即使如果每個基準值將元素分開為99%在一邊和1%在另一邊，呼叫的深度仍然限制在，所以全部執行時間依然是。
然而，在最壞的情況是，兩子數列擁有大各為 和，且呼叫樹（call tree）變成為一個個巢狀（nested）呼叫的線性連串（chain）。第 次呼叫作了的工作量，且遞迴關係式為：
這與插入排序和選擇排序有相同的關係式，以及它被解為。

亂數快速排序的期望複雜度

亂數快速排序有一個值得注意的特性，在任意輸入資料的狀況下，它只需要的期望時間。是什麼讓隨機的基準變成一個好的選擇？
假設我們排序一個數列，然後把它分為四個部份。在中央的兩個部份將會包含最好的基準值；他們的每一個至少都會比25%的元素大，且至少比25%的元素小。如果我們可以一致地從這兩個中央的部份選出一個元素，在到達大小為1的數列前，我們可能最多僅需要把數列分割次，產生一個演算法。
不幸地，亂數選擇只有一半的時間會從中間的部份選擇。出人意外的事實是這樣就已經足夠好了。想像你正在翻轉一枚硬幣，一直翻轉一直到有次人頭那面出現。儘管這需要很長的時間，平均來說只需要次翻動。且在次翻動中得不到次人頭那面的機會，是像天文數字一樣的非常小。藉由同樣的論證，快速排序的遞迴平均只要的呼叫深度就會終止。但是如果它的平均呼叫深度是且每一階的呼叫樹狀過程最多有個元素，則全部完成的工作量平均上是乘積，也就是。

平均複雜度

即使如果我們無法隨機地選擇基準數值，對於它的輸入之所有可能排列，快速排序仍然只需要時間。因為這個平均是簡單地將輸入之所有可能排列的時間加總起來，除以這個因數，相當於從輸入之中選擇一個隨機的排列。當我們這樣作，基準值本質上就是隨機的，導致這個演算法與亂數快速排序有一樣的執行時間。
更精確地說，對於輸入順序之所有排列情形的平均比較次數，可以藉由解出這個遞迴關係式可以精確地算出來。
。
在這裡，是分割所使用的比較次數。因為基準值是相當均勻地落在排列好的數列次序之任何地方，總和就是所有可能分割的平均。
這個意思是，平均上快速排序比理想的比較次數，也就是最好情況下，只大約比較糟39%。這意味著，它比最壞情況較接近最好情況。這個快速的平均執行時間，是快速排序比其他排序演算法有實際的優勢之另一個原因。

選擇的關連性

選擇演算法（selection algorithm）可以選取一個數列的第個最小值；一般而言這是比排序還簡單的問題。一個簡單但是有效率的選擇演算法與快速排序的作法相當類似，除了對兩個子數列都作遞迴呼叫外，它僅僅針對包含想要的元素之子數列作單一的結尾遞迴（tail recursive）呼叫。這個小改變降低了平均複雜度到線性或是時間，且讓它成為一個原地演算法。這個演算法的一種變化版本，可以讓最壞情況下降為（參考選擇演算法來得到更多資訊）。
相反地，一旦我們知道一個最壞情況的選擇演算法是可以利用的，我們在快速排序的每一步可以用它來找到理想的基準（中位數），得到一種最壞情況下執行時間的變化版本。然而在實際的實作中，這種版本一般而言相當慢。

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等於負值時引發段錯誤（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--;               // 移動指針以繼續
            }
        } 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++;
        swap(&arr[left], &arr[end]);
    }
    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 <typename T> // 整數或浮點數皆可使用,若要使用物件(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 <typename T>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 <typename T> //整數或浮點數皆可使用,若要使用物件(class)時必須設定"小於"(<)、"大於"(>)、"不小於"(>=)的運算子功能void quick_sort(T arr[], int len) {
    quick_sort_recursive(arr, 0, len - 1);}

Go

func qsort(data []int) {
if len(data) <= 1 {
return
}
mid := data[0]
head, tail := 0, len(data)-1
for i := 1; i <= tail; {
if data[i] > mid {
data[i], data[tail] = data[tail], data[i]
tail--
} else {
data[i], data[head] = data[head], data[i]
head++
i++
}
}
qsort(data[:head])
qsort(data[head+1:])}

scheme

#lang racket;;快速排序(define quick-sort
 (λ (s)
  (if (< (length s) 2)
   s
   (append
    (quick-sort
(filter
          (λ (e)
    (< e (last s)))
          s))
    (filter
      (λ (e)
        (= e (last s)))
      s)
    (quick-sort
(filter
          (λ (e)
    (> e (last s)))
          s))))))

Common Lisp

(defun filter-< (lst pivot)
  (remove-if-not (lambda (x)
                   (< x pivot)) lst))(defun quick-sort (lst)
  (if (null (cdr lst)) lst
    (let ((pivot (car lst))
          (else (cdr lst)))
      (append
        (quick-sort (filter-< else pivot))
        (list pivot)
        (quick-sort (set-difference
                      else
                      (filter-< else pivot)))))))

Erlang

qsort([]) -> [];qsort([Head|Rest]) ->
qsort([X || X <-Rest, X<Head]) ++ [Head] ++ qsort([X || X <-Rest, X>=Head]).%% @doc 快排假装优化版（这个版本测试比第一个更慢，具体原因大家可以思考下）sort_2([X | L]) ->
    {L1, L2} = sort_2_helper(L, X),
    sort_2(L1) ++ [X] ++ sort_2(L2);sort_2([]) -> [].sort_2_helper(L, X) -> sort_2_helper(L, X, {[], []}).sort_2_helper([Y | L], X, {L1, L2}) when Y =< X -> sort_2_helper(L, X, {[Y | L1], L2});sort_2_helper([Y | L], X, {L1, L2}) -> sort_2_helper(L, X, {L1, [Y | L2]});sort_2_helper([], _X, {L1, L2}) -> {L1, L2}.

Java

public class Application {

    public static void qSort(int[] arr, int head, int tail) {
        if (head >= tail || arr == null || arr.length <= 1) {
            return;
        }
        int i = head, j = tail, pivot = arr[(head + tail) / 2];
        while (i <= j) {
            while (arr[i] < pivot) {
                ++i;
            }
            while (arr[j] > pivot) {
                --j;
            }
            if (i < j) {
                int t = arr[i];
                arr[i] = arr[j];
                arr[j] = t;
                ++i;
                --j;
            } else if (i == j) {
                ++i;
            }
        }
        qSort(arr, head, j);
        qSort(arr, i, tail);
    }

    public static void main(String[] args) {
        int[] arr = new int[]{1, 4, 8, 2, 55, 3, 4, 8, 6, 4, 0, 11, 34, 90, 23, 54, 77, 9, 2, 9, 4, 10};
        qSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }}

Perl

sub qsort {
    return () unless @_;
    (qsort(grep { $_ < $_[0]  } @_[1..$#_]),   $_[0],
     qsort(grep { $_ >= $_[0] } @_[1..$#_]));}

Python原地排序版本

1 def quick_sort(alist, first, last): 2     if first >= last: 3         return 4     mid_value = alist[first] 5     low = first 6     high = last 7     while low < high: 8         while low < high and alist[high] >= mid_value: 9             high -= 110         alist[low] = alist[high]11         while low < high and alist[low] < mid_value:12             low += 113         alist[high] = alist[low]14     alist[low] = mid_value15     quick_sort(alist, first, low-1)16     quick_sort(alist, low+1, last)17 18 numbers = [9, 8, 7, 6, 5, 4, 3, 2, 1, 0]19 quick_sort(numbers，0，len(numbers)-1)20 assert numbers == [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

Python的簡單版本

1 import random 2  3 def quick_sort(numbers): 4     if len(numbers) <= 1: 5         return numbers 6  7     left, right, mid = [], [], [] 8     pivot = random.choice(numbers) 9 10     for number in numbers:11         if number == pivot:12             mid.append(number)13         elif number < pivot:14             left.append(number)15         else:16             right.append(number)17 18     return quick_sort(left) + mid + quick_sort(right)19 20 numbers = [9, 8, 7, 6, 5, 4, 3, 2, 1, 1, 0]21 assert quick_sort(numbers) == [0, 1, 1, 2, 3, 4, 5, 6, 7, 8, 9]

Matlab

1 function sortedArray = quickSort(array) 2     if numel(array) <= 1 
 3         sortedArray = array; 4         return 5     end 6     pivot = array(end); 7     array(end) = []; 8     less = array( array <= pivot ); 9     greater = array( array > pivot );10     sortedArray = [quickSort(less) pivot quickSort(greater)];11 end

Joy

DEFINE sort == [small][]
               [uncons [>] split]
               [[swap] dip cons concat] binrec .

PHP

從尾端取元素作為比較基準
function quick_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];

return array_merge(quick_sort($left), (array)$mid_value, quick_sort($right));}
從正中間取元素作為比較基準
function quick_sort($arr) {
$len = count($arr);

if ($len <= 1)
return $arr;

$left = $right = array();
$mid_index = $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];
}

return array_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 :: (Ord a) = > [a] -> [a]
  
  sort [] = []
  sort (pivot:rest) = sort [y | y <- rest, y < pivot]
                      ++ [pivot] ++ 
                      sort [y | y <- rest, y >=pivot]

Prolog

split(H, [A|X], [A|Y], Z) :-
  order(A, H), split(H, X, Y, Z).split(H, [A|X], Y, [A|Z]) :-
  not(order(A, H)), split(H, X, Y, Z).split(_, [], [], []).quicksort([], X, X).quicksort([H|T], S, X) :-
  split(H, T, A, B),
  quicksort(A, S, [H|Y]),
  quicksort(B, Y, X).

Ruby

def quick_sort(array)
  return array if array.size < 2
  left, 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.
fun quicksort lt lst =
  let val rec sort =
    fn [] => []
     | (x::xs) =>
        let
          val (left,right) = List.partition (fn y => lt (y, x)) xs
        in sort left @ x :: sort right
        end
  in sort lst
end

Pascal

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;
或者
procedure quicksort(var a: array of integer; l,r:integer);var i,j,x,t:integer;begin
 i:=l; j:=r; x:=a[(l+r) div 2];
 repeat
  while a[i]<x do inc(i);
  while a[j]>x 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 i<r then quicksort(a,i,r);
 if l<j then quicksort(a,l,j);end;

C#

public static bool QuickSort(ref int[] arr, int left = 0, int right = -1)
        {
            if (right == -1)
            {
                right = arr.Length - 1;
            }
            if ((right >= 0 && left >= right)|| right > arr.Length - 1)
            {
                return true;
            }
            int container = arr[left];
            int leftContainer = left;
            int rightContainer = right;

            while (left < right)
            {
                while (left < right && arr[right] >= container)
                {
                    right--;
                }
                arr[left++] = arr[right];

                while (left < right && arr[left] <= container)
                {
                    left++;
                }
                arr[right--] = arr[left];
            }
            arr[left] = container;

            return QuickSort(ref arr, leftContainer, left - 1) & QuickSort(ref arr, right + 1, rightContainer);
        }

VB.Net

Public Shared Sub Sort(numbers As Integer())
Sort(numbers, 0, numbers.Length - 1)End SubPrivate Shared Sub Sort(numbers As Integer(), left As Integer, right As Integer)
If left < right Then
Dim middle As Integer = numbers((left + right) \ 2)
Dim i As Integer = left - 1
Dim j As Integer = right + 1 
While True
Do
i+=1
Loop While numbers(i) <= middle

Do
j-=1
Loop While numbers(j) >= middle

If i >= j Then
Exit While
End If

Swap(numbers, i, j)
End While

Sort(numbers, left, i - 1)
Sort(numbers, j + 1, right)
End IfEnd SubPrivate Shared Sub Swap(numbers As Integer(), i As Integer, j As Integer)
Dim number As Integer = numbers(i)
numbers(i) = numbers(j)
numbers(j) = numberEnd Sub

ActionScript

public function qSort(arr:Array):void{
quickSort(arr, 0, arr.length - 1);}private function quickSort(data:Array, left:int, right:int):void{
var temp:Number = data[left];
var p:int = left;
var i:int = left, j:int = right;

while (i <= j)
{
while (data[j] >= temp && j >= p)
j--;
if (j >= p)
{
data[p] = data[j];
p = j;
}

while (data[i] <= temp && i <= p)
i++;
if (i <= p)
{
data[p] = data[i];
p = i;
}
}
data[p] = temp;
if (p - left > 1)
{
quickSort(data, left, p - 1);
}
if (right - p > 1)
{
quickSort(data, p + 1, right);
}}

JavaScript

Array.prototype.quickSort = function() {
    const l = this.length
    if(l < 2) return this
    const basic = this[0], left = [], right = []
    for(let i = 1; i < l; i++) {
      const iv = this[i]
      iv >= basic && right.push(iv) // to avoid repeatly element.
      iv < basic && left.push(iv)
    }
    return left.quickSort().concat(basic, right.quickSort())}const arr = [5, 3, 7, 4, 1, 9, 8, 6, 2];const ascendArr = arr.quickSort()
或
const sort = (x, ...xs) => {
    const sortAgain = f => arr => {
        const res = arr.filter(f)
        return res.length > 0 ? sort(...res) : []
    }

    return xs.length === 0
        ? [x]
        : [...sortAgain(v => v < x)(xs), x, ...sortAgain(v => v >= x)(xs)]}const arr = [7, 2, 6, 1, 2, 8, 4, 9, 0, 9, 7, 5, 4, 2]const ascendArr = sort(...arr)

Rust

fn quick_sort<T: Ord + Copy>(data: &mut [T]) {    let len = data.len();    if len < 2 {        return;    }    let end = len - 1;    let mut cur = 0;    for i in 0..end {        if data[i] < data[end] {            data.swap(cur, i);            cur += 1;        }    }    data.swap(cur, end);    if cur > 1 {        quick_sort(&mut data[0..cur]);    }    if cur + 1 < len {        quick_sort(&mut data[cur + 1..len]);    }}