快速排序

本页使用了标题或全文手工转换
维基百科，自由的百科全书

这是本页的一个历史版本，由220.128.79.49（留言）在2015年1月21日 (三) 09:10 （→‎C）编辑。这可能和当前版本存在着巨大的差异。

快速排序
使用快速排序法對一列數字進行排序的過程
概况
類別排序算法
資料結構不定
复杂度
平均時間複雜度
最坏时间复杂度
最优时间复杂度
空間複雜度根據實現的方式不同而不同
最佳解有时是
相关变量的定义

快速排序是由東尼·霍爾所發展的一種排序算法。在平均狀況下，排序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)的空間。

然而我們在這裡省略一些小的細節。如果我們考慮排序任意很長的數列，我們必須要記住我們的變數像是left和right，不再被認為是佔據固定的空間；也需要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)執行時間的變化版本。然而在實際的實作中，這種版本一般而言相當慢。

實作範例

主条目：快速排序實作

於此我們展示在數種語言下的幾個快速排序實作。我們在此僅展示出最普遍或獨特的一些；針對其他的實作，參見快速排序實作條目。

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)))))))

C++（迭代版本）

//参考：http://www.dutor.net/index.php/2011/04/recursive-iterative-quick-sort/
struct Range{
	explicit Range(int s=0,int e=0):start(s),end(e){}
	int start,end;
};
void quicksort(int n,int arr[]){
	if(n<=0) return;
	stack<Range> st;
	st.push(Range(0,n-1));
	while(!st.empty()){
		Range range = st.top();
		st.pop();
		int pivot = arr[range.end];
		int pos = range.start-1;
		for(int i=range.start;i<range.end;++i){
			if(arr[i]<pivot){
				std::swap(arr[i],arr[++pos]);
			}
		}
		std::swap(arr[++pos],arr[range.end]);
		if(pos-1>range.start){
			st.push(Range(range.start,pos-1));
		}
		if(pos+1<range.end){
			st.push(Range(pos+1,range.end));
		}
	}
}

C

#include <stdio.h>
#include <stddef.h>

void swap(int * a, int * b) {
  int tmp = * a;
  * a = * b;
  * b = tmp;
}

size_t partition(int * ary, size_t len, size_t pivot_i) {
  size_t i = 0;
  size_t small_len = pivot_i;
  int pivot = ary[pivot_i];
  swap(&ary[pivot_i], &ary[pivot_i + (len - 1)]);
  for (; i < len; i++) {
    if (ary[pivot_i + i] < pivot) {
      swap(&ary[pivot_i + i], &ary[small_len]);
      small_len++;
    }
  }
  swap(&ary[pivot_i + (len - 1)], &ary[small_len]);
  return small_len;
}

void quick_sort(int * ary, size_t len) {
  if (len == 0 || len == 1) return;
  size_t small_len = partition(ary, len, 0);
  quick_sort(ary, small_len);
  quick_sort(&ary[small_len + 1], len - small_len - 1);
}

int main(void) {
  int ary[] = {2,4,2,5,3,5,3,1,7,6};
  size_t len = sizeof(ary) / sizeof(ary[0]);
  quick_sort(ary, len);
  return 0;
}


C89标准在stdlib.h中定义了抽象数据类型的快速排序函数qsort(3)。 

#include <stdio.h>
#include <stdlib.h>

static int cmp(const void *a, const void *b)
{
    return *(int *)a - *(int *)b;
}

int main()
{
    int arr[10]={5, 3, 7, 4, 1, 9, 8, 6, 2};

    qsort(arr, 10, sizeof(int), cmp);

    return 0;
}

#include <functional>
#include <algorithm>
#include <iterator>

template< typename BidirectionalIterator, typename Compare >
void quick_sort( BidirectionalIterator first, BidirectionalIterator last, Compare cmp ) {
  if( first != last ) {
    BidirectionalIterator left = first;
    BidirectionalIterator right = last;
    BidirectionalIterator pivot = left++;

    while( left != right ) {
      if( cmp( *left, *pivot ) ) {
         ++left;
      } else {
         while( (left != right) && cmp( *pivot, *right ) )
           right--;
         std::iter_swap( left, right );
      }
    }

    if (cmp( *pivot, *left ))
         --left;
    std::iter_swap( first, left );

    quick_sort( first, left, cmp );
    quick_sort( right, last, cmp );
  }
}

template< typename BidirectionalIterator >
inline void quick_sort( BidirectionalIterator first, BidirectionalIterator last ) {
  quick_sort( first, last,
    std::less_equal< typename std::iterator_traits< BidirectionalIterator >::value_type >()
  );
}

未使用STL的快速排序版本。 

#include <utility>
using std::swap;

int partition(int* array, int left, int right)
{
	int index = left;
	int pivot = array[index];	
	swap(array[index], array[right]);
	for (int i=left; i<right; i++)
	{
		if (array[i] > pivot)    // 降序
			swap(array[index++], array[i]);
	}
	swap(array[right], array[index]);
	return index;
}

void qsort(int* array, int left, int right)
{
	if (left >= right) 
		return;
	int index = partition(array, left, right);
	qsort(array, left, index - 1);
	qsort(array, index + 1, right);
}

Erlang

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

Java

import java.util.Comparator;
import java.util.Random;

public class Quicksort {
    public static final Random RND = new Random();

    private static void swap(Object[] array, int i, int j) {
        Object tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }

    private static <E> int partition(E[] array, int begin, int end, Comparator<? super E> cmp) {
        int index = begin + RND.nextInt(end - begin + 1);
        E pivot = array[index];
        swap(array, index, end);	
        for (int i = index = begin; i < end; ++ i) {
            if (cmp.compare(array[i], pivot) <= 0) {
                swap(array, index++, i);
            }
        }
        swap(array, index, end);	
        return (index);
    }

    private static <E> void qsort(E[] array, int begin, int end, Comparator<? super E> cmp) {
        if (end > begin) {
            int index = partition(array, begin, end, cmp);
            qsort(array, begin, index - 1, cmp);
            qsort(array, index + 1,  end,  cmp);
        }
    }

    public static <E> void sort(E[] array, Comparator<? super E> cmp) {
        qsort(array, 0, array.length - 1, cmp);
    }

}

/*
 * more efficient implements for quicksort. <br />
 * use left, center and right median value (@see #median()) for the pivot, and
 * the more efficient inner loop for the core of the algorithm.
 */
class Sort {

     public static final int CUTOFF = 11;

    /**
     * quick sort algorithm. <br />
     * 
     * @param arr an array of Comparable items. <br />
     */
     public static <T extends Comparable<? super T>> void quicksort( T[] arr ) {
	 quickSort( arr, 0, arr.length - 1 );
     }


     /**
      * get the median of the left, center and right. <br />
      * order these and hide the pivot by put it the end of
      * of the array. <br />
      * 
      * @param arr an array of Comparable items. <br />
      * @param left the most-left index of the subarray. <br />
      * @param right the most-right index of the subarray.<br />
      * @return T
      */
      public static <T extends Comparable<? super T>> T median( T[] arr, int left, int right ) {
		
		int center = ( left + right ) / 2;
		
		if ( arr[left].compareTo( arr[center] ) > 0 )
			swapRef( arr, left, center );
		if ( arr[left].compareTo( arr[right] ) > 0 )
			swapRef( arr, left, right );
		if ( arr[center].compareTo( arr[right] ) > 0 )
			swapRef( arr, center, right );
		
		swapRef( arr, center, right - 1 );
		return arr[ right - 1 ];
      }

     /**
      * internal method to sort the array with quick sort algorithm. <br />
      * 
      * @param arr an array of Comparable Items. <br />
      * @param left the left-most index of the subarray. <br />
      * @param right the right-most index of the subarray. <br />
      */
      private static <T extends Comparable<? super T>> void quickSort( T[] arr, int left, int right ) {
		if ( left + CUTOFF <= right  ) {
			//find the pivot
			T pivot = median( arr, left, right );
			
			//start partitioning
			int i = left, j = right - 1;
			for ( ; ; ) {
				while ( arr[++i].compareTo( pivot ) < 0 ) ;
				while ( arr[--j].compareTo( pivot ) > 0 ) ;
				if ( i < j )
					swapRef( arr, i, j );
				else
					break;
			}
			
			//swap the pivot reference back to the small collection.
			swapRef( arr, i, right - 1 );
			
			quickSort( arr, left, i - 1 );		//sort the small collection.
			quickSort( arr, i + 1, right );		//sort the large collection.
			
		} else {
			//if the total number is less than CUTOFF we use insertion sort instead (cause it much more efficient).
			insertionSort( arr, left, right );
		}
      }


      /**
       * method to swap references in an array.<br />
       * 
       * @param arr an array of Objects. <br />
       * @param idx1 the index of the first element. <br />
       * @param idx2 the index of the second element. <br />
       */
      public static <T> void swapRef( T[] arr, int idx1, int idx2 ) {
		T tmp = arr[idx1];
		arr[idx1] = arr[idx2];
		arr[idx2] = tmp;
      }


      /**
       * method to sort an subarray from start to end
       * 		with insertion sort algorithm. <br />
       * 
       * @param arr an array of Comparable items. <br />
       * @param start the begining position. <br />
       * @param end the end position. <br />
       */
      public static <T extends Comparable<? super T>> void insertionSort( T[] arr, int start, int end ) {
		int i;
		for ( int j = start + 1; j <= end; j++ ) {
			T tmp = arr[j];
			for ( i = j; i > start && tmp.compareTo( arr[i - 1] ) < 0; i-- ) {
				arr[ i ] = arr[ i - 1 ];
			}
			arr[ i ] = tmp;
		}
      }
}

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 quicksort($seq) {
  if (count($seq) > 1) {
    $k = $seq[0];
    $x = array();
    $y = array();
    $_size = count($seq);      //do not use count($seq) in loop for.
    for ($i=1; $i<$_size; $i++) {
      if ($seq[$i] <= $k) {
        $x[] = $seq[$i];
      } else {
        $y[] = $seq[$i];
      }
    }
    $x = quicksort($x);
    $y = quicksort($y);
    return array_merge($x, array($k), $y);
  } else {
    return $seq;
  }
}

PHP Another

$list = array(85, 24, 63, 45,55, 17, 31, 96, 50);

print_r(qsort($list));

function qsort($arr) {
    $len = count($arr);

    if($len <=1 ) return $arr;
    
    $left = $right = array();
    $mid_index = floor($len/2);
    $mid_value = $arr[$mid_index];

    for($i=0;$i<$len;$i++){
        if($i==$mid_index)continue;

        //seperate elements by 'mid_value'
        if($arr[$i] < $mid_value){
            $left[] = $arr[$i];
        }else{
            $right[] = $arr[$i];
        }
    }
    
    return array_merge(qsort($left),(array)$mid_value,qsort($right));
}
#######output#########
#Array ( [0] => 17 [1] => 24 [2] => 31 [3] => 45 [4] => 50 [5] => 55 [6] => 63 [7] => 85 [8] => 96 )

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 sort(array)
  # return [] if array.empty?
  return array if array.size < 2
  left, right = array[1..-1].partition { |y| y <= array.first }
  sort(left) + [ array.first ] + sort(right)
end

SML

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

	function quickSort(arr,campfunc,left,right){
		if(arguments.length <2){
			campfunc = quickSort.comp;
		}
		if(arguments.length != 4){
			left = 0;
			right = arr.length -1;
		}
		
		if(left > right){
			return ;
		}
		
		var index = quickSort.partition(arr,campfunc,left,right);
		quickSort(arr,campfunc,left,index-1);
		quickSort(arr,campfunc,index + 1, right);
	}
	
	quickSort.comp = function (a,b){
		return a > b;
	};
	
	quickSort.swap = function (arr,lIndex,rIndex){
		var temp = arr[lIndex];
		arr[lIndex] = arr[rIndex];
		arr[rIndex] = temp;
	};
	
	quickSort.partition = function (arr,campfunc,left,right){
		var index = left;
		var pivot = arr[index];
		quickSort.swap(arr,index,right);
		
		for(var i = left; i < right; i++){
			if(campfunc(arr[i],pivot)){
				quickSort.swap(arr,index++,i);
			}
		}
		quickSort.swap(arr,right,index);
		return index;
	};
	

	var arr = [5, 3, 7, 4, 1, 9, 8, 6, 2];
	quickSort(arr,function(a,b){return a < b;});
	console.log(arr);

外部連結

參考

  • 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.

理论
交换排序
选择排序
插入排序
归并排序
分布排序
并发排序
混合排序
其他
取自“https://zh.wikipedia.org/w/index.php?title=快速排序&oldid=34039029”