本页使用了标题或全文手工转换

快速排序

维基百科,自由的百科全书
跳转至: 导航搜索
快速排序
Sorting quicksort anim.gif
使用快速排序法對一列數字進行排序的過程
分类 排序算法
数据结构 不定
时间复杂度
最优时间复杂度
平均时间复杂度
空间复杂度 根據實現的方式不同而不同

快速排序英语:Quicksort),又稱劃分交換排序partition-exchange sort),一種排序算法,最早由東尼·霍爾提出。在平均狀況下,排序n個項目要Ο(n log n)次比較。在最壞狀況下則需要Ο(n2)次比較,但這種狀況並不常見。事實上,快速排序通常明顯比其他Ο(n log n)演算法更快,因為它的內部循环(inner loop)可以在大部分的架構上很有效率地被实现出來。

演算法[编辑]

快速排序采用「分而治之、各個擊破」的觀念,此为原地(In-place)分割版本。

快速排序使用分治法(Divide and conquer)策略來把一個序列(list)分為兩個子序列(sub-lists)。

步驟為:

  1. 從數列中挑出一個元素,稱為"基準"(pivot),
  2. 重新排序數列,所有元素比基準值小的擺放在基準前面,所有元素比基準值大的擺在基準的後面(相同的數可以到任一邊)。在這個分割結束之後,該基準就處於數列的中間位置。這個稱為分割(partition)操作。
  3. 递归地(recursive)把小於基准值元素的子數列和大於基准值元素的子數列排序。

遞迴的最底部情形,是數列的大小是零或一,也就是永遠都已經被排序好了。雖然一直遞迴下去,但是這個演算法總會結束,因為在每次的迭代(iteration)中,它至少會把一個元素擺到它最後的位置去。


在简单的伪代码中,此算法可以被表示为:

 function quicksort(q)
     var list less, pivotList, greater
     if length(q) ≤ 1 {
         return q
     } else {
         select a pivot value pivot from q
         for each x in q except the pivot element
             if x < pivot then add x to less
             if x ≥ pivot then add x to greater
         add pivot to pivotList
         return concatenate(quicksort(less), pivotList, quicksort(greater))
     }

原地(in-place)分割的版本[编辑]

上面簡單版本的缺點是,它需要Ω(n)的額外儲存空間,也就跟归并排序一樣不好。額外需要的記憶體空間配置,在實際上的實作,也會極度影響速度和快取的效能。有一個比較複雜使用原地(in-place)分割算法的版本,且在好的基準選擇上,平均可以達到O(log n)空間的使用複雜度。

 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)。堆排序通常比快速排序稍微慢,但是最壞情況的執行時間總是O(n log n)。快速排序是經常比較快,除了introsort變化版本外,仍然有最壞情況效能的機會。如果事先知道堆排序將會是需要使用的,那麼直接地使用堆排序比等待introsort再切換到它還要快。堆排序也擁有重要的特點,僅使用固定額外的空間(堆排序是原地排序),而即使是最佳的快速排序變化版本也需要Θ(log n)的空間。然而,堆排序需要有效率的隨機存取才能變成可行。

快速排序也與归并排序(Mergesort)競爭,這是另外一種遞迴排序算法,但有壞情況O(n log n)執行時間的優勢。不像快速排序或堆排序,归并排序是一個穩定排序,且可以輕易地被採用在链表(linked list)和儲存在慢速存取媒體上像是磁碟儲存網路連接儲存的非常巨大數列。儘管快速排序可以被重新改寫使用在鍊串列上,但是它通常會因為無法隨機存取而導致差的基準選擇。归并排序的主要缺點,是在最佳情況下需要Ω(n)額外的空間。

正規分析[编辑]

從一開始快速排序平均需要花費O(n log n)時間的描述並不明顯。但是不難觀察到的是分割運算,陣列的元素都會在每次迴圈中走訪過一次,使用O(n)的時間。在使用結合(concatenation)的版本中,這項運算也是O(n)。

在最好的情況,每次我們執行一次分割,我們會把一個數列分為兩個幾近相等的片段。這個意思就是每次遞迴调用處理一半大小的數列。因此,在到達大小為一的數列前,我們只要作log n次巢狀的调用。這個意思就是调用樹的深度是O(log n)。但是在同一階層的兩個程序调用中,不會處理到原來數列的相同部份;因此,程序调用的每一階層總共全部僅需要O(n)的時間(每個调用有某些共同的額外耗費,但是因為在每一階層僅僅只有O(n)個调用,這些被歸納在O(n)係數中)。結果是這個演算法僅需使用O(n log n)時間。

另外一個方法是為T(n)設立一個遞迴關係式,也就是需要排序大小為n的數列所需要的時間。在最好的情況下,因為一個單獨的快速排序调用牽涉了O(n)的工作,加上對n/2大小之數列的兩個遞迴调用,這個關係式可以是:

T(n) = O(n) + 2T(n/2)

解決這種關係式型態的標準数学归纳法技巧告訴我們T(n) = O(n log n)。

事實上,並不需要把數列如此精確地分割;即使如果每個基準值將元素分開為99%在一邊和1%在另一邊,调用的深度仍然限制在100log n,所以全部執行時間依然是O(n log n)。

然而,在最壞的情況是,兩子數列擁有大各為1和n-1,且调用樹(call tree)變成為一個n個巢狀(nested)呼叫的線性連串(chain)。第i次呼叫作了O(n-i)的工作量,且遞迴關係式為:

T(n) = O(n) + T(1) + T(n - 1) = O(n) + T(n - 1)

這與插入排序选择排序有相同的關係式,以及它被解為T(n) = O(n2)。

亂數快速排序的期望複雜度[编辑]

亂數快速排序有一個值得注意的特性,在任意輸入資料的狀況下,它只需要O(n log n)的期望時間。是什麼讓隨機的基準變成一個好的選擇?

假設我們排序一個數列,然後把它分為四個部份。在中央的兩個部份將會包含最好的基準值;他們的每一個至少都會比25%的元素大,且至少比25%的元素小。如果我們可以一致地從這兩個中央的部份選出一個元素,在到達大小為1的數列前,我們可能最多僅需要把數列分割2log2 n次,產生一個O(nlogn)演算法。

不幸地,亂數選擇只有一半的時間會從中間的部份選擇。出人意外的事實是這樣就已經足夠好了。想像你正在翻轉一枚硬幣,一直翻轉一直到有k次人頭那面出現。儘管這需要很長的時間,平均來說只需要2k次翻動。且在100k次翻動中得不到k次人頭那面的機會,是像天文數字一樣的非常小。藉由同樣的論證,快速排序的遞迴平均只要2(2log2 n)的呼叫深度就會終止。但是如果它的平均呼叫深度是O(log n)且每一階的呼叫樹狀過程最多有n個元素,則全部完成的工作量平均上是乘積,也就是O(n log n)。

平均複雜度[编辑]

即使如果我們無法隨機地選擇基準數值,對於它的輸入之所有可能排列,快速排序仍然只需要O(n log n)時間。因為這個平均是簡單地將輸入之所有可能排列的時間加總起來,除以n這個因數,相當於從輸入之中選擇一個隨機的排列。當我們這樣作,基準值本質上就是隨機的,導致這個演算法與亂數快速排序有一樣的執行時間。

更精確地說,對於輸入順序之所有排列情形的平均比較次數,可以藉由解出這個遞迴關係式可以精確地算出來。

在這裡,n-1是分割所使用的比較次數。因為基準值是相當均勻地落在排列好的數列次序之任何地方,總和就是所有可能分割的平均。

這個意思是,平均上快速排序比理想的比較次數,也就是最好情況下,只大約比較糟39%。這意味著,它比最壞情況較接近最好情況。這個快速的平均執行時間,是快速排序比其他排序演算法有實際的優勢之另一個原因。

空間複雜度[编辑]

被快速排序所使用的空間,依照使用的版本而定。使用原地(in-place)分割的快速排序版本,在任何遞迴呼叫前,僅會使用固定的額外空間。然而,如果需要產生O(log n)巢狀遞迴呼叫,它需要在他們每一個儲存一個固定數量的資訊。因為最好的情況最多需要O(log n)次的巢狀遞迴呼叫,所以它需要O(log n)的空間。最壞情況下需要O(n)次巢狀遞迴呼叫,因此需要O(n)的空間。

然而我們在這裡省略一些小的細節。如果我們考慮排序任意很長的數列,我們必須要記住我們的變數像是leftright,不再被認為是佔據固定的空間;也需要O(log n)對原來一個n項的數列作索引。因為我們在每一個堆疊框架中都有像這些的變數,實際上快速排序在最好跟平均的情況下,需要O(log2 n)空間的位元數,以及最壞情況下O(n log n)的空間。然而,這並不會太可怕,因為如果一個數列大部份都是不同的元素,那麼數列本身也會佔據O(n log n)的空間位元組。

非原地版本的快速排序,在它的任何遞迴呼叫前需要使用O(n)空間。在最好的情況下,它的空間仍然限制在O(n),因為遞迴的每一階中,使用與上一次所使用最多空間的一半,且

它的最壞情況是很恐怖的,需要

空間,遠比數列本身還多。如果這些數列元素本身自己不是固定的大小,這個問題會變得更大;舉例來說,如果數列元素的大部份都是不同的,每一個將會需要大約O(log n)為原來儲存,導致最好情況是O(n log n)和最壞情況是O(n2 log n)的空間需求。

選擇的關連性[编辑]

選擇算法(selection algorithm)可以選取一個數列的第k個最小值;一般而言這是比排序還簡單的問題。一個簡單但是有效率的選擇算法與快速排序的作法相當類似,除了對兩個子數列都作遞迴呼叫外,它僅僅針對包含想要的元素之子數列作單一的結尾遞迴(tail recursive)呼叫。這個小改變降低了平均複雜度到線性或是Θ(n)時間,且讓它成為一個原地算法。這個算法的一種變化版本,可以讓最壞情況下降為O(n)(參考選擇算法來得到更多資訊)。

相反地,一旦我們知道一個最壞情況的O(n)選擇算法是可以利用的,我們在快速排序的每一步可以用它來找到理想的基準(中位數),得到一種最坏情況下O(n log n)執行時間的變化版本。然而在實際的實作中,這種版本一般而言相當慢。

實作範例[编辑]

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等於負值時宣告堆疊陣列當機
	//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.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--;
			swap(&arr[left], &arr[right]);
		}
		if (arr[left] >= arr[range.end])
			swap(&arr[left], &arr[range.end]);
		else
			left++;
		r[p++] = new_Range(range.start, left - 1);
		r[p++] = new_Range(left + 1, 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++[编辑]

迭代法

//参考: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, i := data[0], 1
	head, tail := 0, len(data)-1
	for head < 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++
		}
	}
	data[head] = mid
	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)))))))

Clojure[编辑]

; 完整的快速排序實現,包含全部依賴關係

; 合併兩個列表 (append [1 2] [3 4]) -> [1 2 3 4]

(def append (lambda [x y] (cond
    [(eq x []) y]
    [#true (cons (car x) (*lambda* (cdr x) y))]
)))

; 規約
; (reduce (lambda [a b] (mul a b)) [1 2 3 4 5]) -> 5

(def reduce (lambda [Fn L] (cond
    [(not-eq L []) ((lambda [n Fn L] (cond
        [(eq L []) n]
        [#true (*lambda* (Fn n (car L)) Fn (cdr L))]
    )) (car L) Fn (cdr L))]
)))

; 合併任意多個列表 (appendn [1 2] [3 4] [5 6] [7 8]) -> [1 2 3 4 5 6 7 8]

(def appendn (lambda [] (reduce append *args*)))

; 過濾,取L中元素依次作為Fn的參數,只在Fn返回#true時保留元素
; (filter (lambda [x] (> x 1800)) [322 629 753 1225 1707 1818 1939 3383 3639 3875]) ->
; [1818 1939 3383 3639 3875]

(def filter (lambda [Fn L] (cond
    [(eq L []) []]
    [(eq (Fn (car L)) #true) (cons (car L) (*lambda* Fn (cdr L)))]
    [#true (*lambda* Fn (cdr L))]
)))

; 比較,若干名字定義

(def ge (lambda [a b] (not (lt a b))))
(def le (lambda [a b] (not (gt a b))))
(def not-eq (lambda [a b] (not (eq a b))))
(def < lt)
(def > gt)
(def >= ge)
(def <= le)

; 自增,即加1

(def inc (lambda [x] (add x 1)))

; 求列表長度

(def length (lambda [L]
    ((lambda [count L] (cond
        [(eq L []) count]
        [#true (*lambda* (inc count) (cdr L))]
    )) 0 L)
))

; 通用快速排序實現,Fn作用于L中的元素,並返回用於排序的值
; 對於 (qsort0 [[2 23] [1 43] [5 23] [4 21] [3 54]] (lambda [E] (car E)))
; 取其中一項為[2 23]
; 求((lambda [E] (car E)) [2 23]) -> 2
; 依此類推
; 最終結果為 [[1 43] [2 23] [3 54] [4 21] [5 23]]

(def qsort0 (lambda [L Fn] (cond
    [(<= (length L) 1) L]
    [#true (appendn
        (*lambda* (filter (lambda [i] (< (Fn i) (Fn (car L)))) (cdr L)) Fn)
        [(car L)]
        (*lambda* (filter (lambda [i] (>= (Fn i) (Fn (car L)))) (cdr L)) Fn)
    )]
)))

; 常函數

(def const (lambda [n] n))

; 對於數列的快速排序, 對於[2 3 4 ...],取其中元素2,帶入常函數(const 2)仍得2,以此排序
; (qsort-number [1818 3875 1225 753 3383 1707 3639 1939 322 629]) ->
;    [322 629 753 1225 1707 1818 1939 3383 3639 3875]

(def qsort-number (lambda [L] (qsort0 L const)))

; 合併所有中間定義,僅僅使用元算子,得到

(lambda [L] ((lambda [L Fn] (cond [((lambda [a b] (not (gt a b))) ((lambda [L] ((lambda [count L] (cond [(eq L 
[]) count] [#true (*lambda* ((lambda [x] ((lambda [] ((lambda [Fn L] (cond [((lambda [a b] (not (eq a b))) L 
[]) ((lambda [n Fn L] (cond [(eq L []) n] [#true (*lambda* (Fn n (car L)) Fn (cdr L))])) (car L) Fn (cdr L))])) 
add *args*)) x 1)) count) (cdr L))])) 0 L)) L) 1) L] [#true ((lambda [] ((lambda [Fn L] (cond [((lambda [a b] 
(not (eq a b))) L []) ((lambda [n Fn L] (cond [(eq L []) n] [#true (*lambda* (Fn n (car L)) Fn (cdr L))])) (car 
L) Fn (cdr L))])) (lambda [x y] (cond [(eq x []) y] [#true (cons (car x) (*lambda* (cdr x) y))])) *args*)) 
(*lambda* ((lambda [Fn L] (cond [(eq L []) []] [(eq (Fn (car L)) #true) (cons (car L) (*lambda* Fn (cdr L)))] 
[#true (*lambda* Fn (cdr L))])) (lambda [i] (lt (Fn i) (Fn (car L)))) (cdr L)) Fn) [(car L)] (*lambda* ((lambda 
[Fn L] (cond [(eq L []) []] [(eq (Fn (car L)) #true) (cons (car L) (*lambda* Fn (cdr L)))] [#true (*lambda* Fn 
(cdr L))])) (lambda [i] ((lambda [a b] (not (lt a b))) (Fn i) (Fn (car L)))) (cdr L)) Fn))])) L (lambda [n] n)))

; 以上就是對於數列的快速排序算法的完整實現

Erlang[编辑]

qsort([]) -> [];
qsort([Head|Rest]) ->
	qsort([X || X <-Rest, X<Head]) ++ [Head] ++ qsort([X || X <-Rest, X>=Head]).

Java[编辑]

class quick_sort {
	int[] arr;

	private void swap(int x, int y) {
		int temp = arr[x];
		arr[x] = arr[y];
		arr[y] = temp;
	}

	private void quick_sort_recursive(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(left, right);
		}
		if (arr[left] >= arr[end])
			swap(left, end);
		else
			left++;
		quick_sort_recursive(start, left - 1);
		quick_sort_recursive(left + 1, end);
	}

	public void sort(int[] arrin) {
		arr = arrin;
		quick_sort_recursive(0, arr.length - 1);
	}
}

Perl[编辑]

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

Python[编辑]

def qsort(arr):
    if len(arr) <= 1:
        return arr
    else:
        pivot = arr[0]
        return qsort([x for x in arr[1:] if x < pivot]) + \
               [pivot] + \
               qsort([x for x in arr[1:] if x >= pivot])

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 void Sort(int[] numbers)
{
    Sort(numbers, 0, numbers.Length - 1);
}

private static void Sort(int[] numbers, int left, int right)
{
    if (left < right)
    {
        int middle = numbers[(left + right) / 2];
        int i = left - 1;
        int j = right + 1;
        while (true)
        {
            while (numbers[++i] < middle) ;

            while (numbers[--j] > middle) ;

            if (i >= j)
                break;

            Swap(numbers, i, j);
        }

        Sort(numbers, left, i - 1);
        Sort(numbers, j + 1, right);
    }
}

private static void Swap(int[] numbers, int i, int j)
{
    int number = numbers[i];
    numbers[i] = numbers[j];
    numbers[j] = number;
}

VB.Net[编辑]

Public Shared Sub Sort(numbers As Integer())
	Sort(numbers, 0, numbers.Length - 1)
End Sub

Private 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 If
End Sub

Private Shared Sub Swap(numbers As Integer(), i As Integer, j As Integer)
	Dim number As Integer = numbers(i)
	numbers(i) = numbers(j)
	numbers(j) = number
End 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.quick_sort = function() {
	var len = this.length;
	if (len <= 1)
		return this.slice(0);
	var left = [];
	var right = [];
	var mid = [this[0]];
	for (var i = 1; i < len; i++)
		if (this[i] < mid[0])
			left.push(this[i]);
		else
			right.push(this[i]);
	return left.quick_sort().concat(mid.concat(right.quick_sort()));
};

var arr = [5, 3, 7, 4, 1, 9, 8, 6, 2];
arr = arr.quick_sort();
for (i = 0; i < arr.length; i++)
	document.body.innerHTML += arr[i] + " ";
document.body.innerHTML += "<br>";

外部連結[编辑]

參考[编辑]

  • Hoare, C. A. R. "Partition: Algorithm 63," "Quicksort: Algorithm 64," and "Find: Algorithm 65." Comm. ACM 4, 321-322, 1961
  • R. Sedgewick. Implementing quicksort programs, Communications of the ACM, 21(10):847857, 1978.
  • David Musser. Introspective Sorting and Selection Algorithms, Software Practice and Experience vol 27, number 8, pages 983-993, 1997
  • A. LaMarca and R. E. Ladner. "The Influence of Caches on the Performance of Sorting." Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 1997. pp. 370–379.
  • Faron Moller. Analysis of Quicksort. CS 332: Designing Algorithms. Department of Computer Science, University of Wales Swansea.
  • Steven Skiena. Lecture 5 - quicksort. CSE 373/548 - Analysis of Algorithms. Department of Computer Science. SUNY Stony Brook.

註腳[编辑]

1. David M. W. Powers. Parallelized Quicksort with Optimal Speedup. Proceedings of International Conference on Parallel Computing Technologies. Novosibirsk. 1991.