[科普中國]-快速排序算法

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

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

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

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

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

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

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

排序步驟原理設要排序的數(shù)組是A[0]……A[N-1]，首先任意選取一個數(shù)據(jù)（通常選

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

一趟快速排序的算法是：1

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

2）以第一個數(shù)組元素作為關(guān)鍵數(shù)據(jù)，賦值給key，即key=A[0]；1

3）從j開始向前搜索，即由后開始向前搜索(j--)，找到第一個小于key的值A(chǔ)[j]，將A[j]和A[i]的值交換；1

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

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-完成的時候，此時令循環(huán)結(jié)束）。1

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

此時，ref=5，i=1，j=11，從后往前找，第一個比5小的數(shù)是x8=2，因此序列為：2，3，7，6，4，1，0，5，9，10，8。此時i=1，j=8，從前往后找，第一個比5大的數(shù)是x3=7，因此序列為：2，3，5，6，4，1，0，7，9，10，8。此時，i=3，j=8，從第8位往前找，第一個比5小的數(shù)是x7=0，因此：2，3，0，6，4，1，5，7，9，10，8。此時，i=3，j=7，從第3位往后找，第一個比5小的數(shù)是x4=6，因此：2，3，0，5，4，1，6，7，9，10，8。此時，i=4，j=7，從第7位往前找，第一個比5小的數(shù)是x6=1，因此：2，3，0，1，4，5，6，7，9，10，8。此時，i=4，j=6，從第4位往后找，直到第6位才有比5大的數(shù)，這時，i=j=6，ref成為一條分界線，它之前的數(shù)都比它小，之后的數(shù)都比它大，對于前后兩部分數(shù)，可以采用同樣的方法來排序。3

程序調(diào)用舉例用法:3

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

參數(shù)：
1、待排序數(shù)組首地址；3

2、數(shù)組中待排序元素數(shù)量；3

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

4、指向函數(shù)的指針，用于確定排序的順序。3

示例代碼GO// 第一種寫法func quickSort(values []int, left, right int) { temp := values[left] p := left i, j := left, right for i = p && values[j] >= temp { j-- } if j >= p { values[p] = values[j] p = j } for i q_sort([X||Xq_sort [a|a