快速排序

趟排序将要排序的資料分割成獨立的兩部分，其中一部分的所有資料都比另外一部分的所有資料都要小，然 後

列。

用一句話來說，快速排序就是運用了 “分而治之” 和 “遞歸”的方法！

算法過程（轉自百度百科）設要排序的數組是A[0]……A[N-1]，首先任意選取一個資料（通常選用第一個資料）作 為關鍵資料，然

後将所有比它小的數都放到它前面，所有比它大的數都放到它後面，這個過程稱為一趟快速排序。一趟快速

排序的算法是：

1）設定兩個變量I、J，排序開始的時候：I=0，J=N-1；

2）以第一個數組元素作為關鍵資料，指派給key，即 key=A[0]；

3）從J開始向前搜尋，即由後開始向前搜尋（J=J-1），找到第一個小于key的值 a[j]，并與key交換；

4）從I開始向後搜尋，即由前開始向後搜尋（I=I+1），找到第一個大于key的a[i]， 與key交換；

5）重複第3、4、5步，直到 I=J； (3,4步是在程式中沒找到時候j=j-1，i=i+1。找到并交換的時候i， j指

針位置不變。另外當i=j這過程一定正好是i+或j+完成的最後另循環結束)

例如：待排序的數組A的值分别是：（初始關鍵資料：X=49） 注意關鍵X永遠不變.永遠是和X進行比較

無論在什麼位子 最後的目的就是把X放在中間小的放前面大的放後面

A[0] 、 A[1]、 A[2]、 A[3]、 A[4]、 A[5]、 A[6]：

49 38 65 97 76 13 27

進行第一次交換後： 27 38 65 97 76 13 49

( 按照算法的第三步從後面開始找)

進行第二次交換後： 27 38 49 97 76 13 65

( 按照算法的第四步從前面開始找>X的值，65>49,兩者交換，此時：I=3 )

進行第三次交換後： 27 38 13 97 76 49 65

( 按照算法的第五步将又一次執行算法的第三步從後開始找

進行第四次交換後： 27 38 13 49 76 97 65

( 按照算法的第四步從前面開始找大于X的值，97>49,兩者交換，此時：J=4 )

此時再執行第三步的時候就發現I=J，進而結束一趟快速排序，那麼經過一趟快速排序之後的結果

是：27 38 13 49 76 97 65，即是以大于49的數全部在49的後面，是以小于49的數全部在49的前面。

快速排序就是遞歸調用此過程——在以49為中點分割這個資料序列，分别對前面一部分和後面一部 分

進行類似的快速排序，進而完成全部資料序列的快速排序，最後把此資料序列變成一個有序的序列，根據這

種思想對于上述數組A的快速排序的全過程如圖6所 示：

初始狀态 {49 38 65 97 76 13 27}

進行一次快速排序之後劃分為 {27 38 13} 49 {76 97 65}

分别對前後兩部分進行快速排序 {27 38 13} 經第三步和第四步交換後變成 {13 27 38} 完成排序。

{76 97 65} 經第三步和第四步交換後變成 {65 76 97} 完成排序。

c語言源程式

#include  <stdio.h>

void swap(int *a,int *b);

int partition(int a[],int low,int high);

void quicksort(int a[],int low,int high);

int main()

{

int i;

int a[]={12,5,8,2,9,1};

quicksort(a,0,5);

for(i=0;i<6;i++)

printf("%d ",a[i]);

system("pause");

return 0;

}

void swap(int *a,int *b)

int temp = *a;

*a = *b;

*b = temp;

int partition(int a[],int low,int high)

int pivot = a[low];

while(low <high)

while(low<high&&a[high]>=pivot)

--high;

swap(&a[low],&a[high]);

while(low<high&&a[low]<=pivot)

++low;

return low;

void quicksort(int a[],int low,int high)

if(low<high)

int n = partition(a,low,high);

quicksort(a,low,n);

quicksort(a,n+1,high);