快速排序是對(duì)冒泡法排序的一種改進(jìn),。

快速排序算法 的基本思想是：將所要進(jìn)行排序的數(shù)分為左右兩個(gè)部分,，其中一部分的所有數(shù)據(jù)都比另外一 部分的數(shù)據(jù)小，然后將所分得的兩部分?jǐn)?shù)據(jù)進(jìn)行同樣的劃分，重復(fù)執(zhí)行以上的劃分操作,，直 到所有要進(jìn)行排序的數(shù)據(jù)變?yōu)橛行驗(yàn)橹埂?br>
可能僅根據(jù)基本思想對(duì)快速排序的認(rèn)識(shí)并不深,，接下來以對(duì)n個(gè)無(wú)序數(shù)列A[0], A[1]…, A[n-1]采用快速排序方法進(jìn)行升序排列為例進(jìn)行講解。

(1)定義兩個(gè)變量low和high,，將low,、high分別設(shè)置為要進(jìn)行排序的序列的起始元素和最后一個(gè)元素的下標(biāo)。第一次,，low和high的取值分別為0和n-1,，接下來的每次取值由劃分得到的序列起始元素和最后一個(gè)元素的下標(biāo)來決定。

(2)定義一個(gè)變量key,，接下來以key的取值為基準(zhǔn)將數(shù)組A劃分為左右兩個(gè)部分,，通 常，key值為要進(jìn)行排序序列的第一個(gè)元素值,。第一次的取值為A[0],，以后毎次取值由要?jiǎng)?分序列的起始元素決定。

(3)從high所指向的數(shù)組元素開始向左掃描,，掃描的同時(shí)將下標(biāo)為high的數(shù)組元素依次與劃分基準(zhǔn)值key進(jìn)行比較操作,，直到high不大于low或找到第一個(gè)小于基準(zhǔn)值key的數(shù)組元素，然后將該值賦值給low所指向的數(shù)組元素,，同時(shí)將low右移一個(gè)位置,。

(4)如果low依然小于high，那么由low所指向的數(shù)組元素開始向右掃描,，掃描的同時(shí)將下標(biāo)為low的數(shù)組元素值依次與劃分的基準(zhǔn)值key進(jìn)行比較操作,，直到low不小于high或找到第一個(gè)大于基準(zhǔn)值key的數(shù)組元素，然后將該值賦給high所指向的數(shù)組元素,，同時(shí)將high左移一個(gè)位置,。

(5)重復(fù)步驟(3) (4)，直到low的植不小于high為止,，這時(shí)成功劃分后得到的左右兩部分分別為A[low……pos-1]和A[pos+1……h(huán)igh],，其中，pos下標(biāo)所對(duì)應(yīng)的數(shù)組元素的值就是進(jìn)行劃分的基準(zhǔn)值key,，所以在劃分結(jié)束時(shí)還要將下標(biāo)為pos的數(shù)組元素賦值 為 key,。

(6)將劃分得到的左右兩部分A[low……pos-1]和A[pos+1……h(huán)igh]繼續(xù)采用以上操作步驟進(jìn)行劃分，直到得到有序序列為止,。

為了能夠加深讀者的理解,，接下來通過一段代碼來了解快速排序的具體實(shí)現(xiàn)方法。

1. #include
2. #include
3. #define N 6
5. int partition(int arr[], int low, int high){
6. int key;
7. key = arr[low];
8. while(lowhigh){
9. while(low high && arr[high]>= key )
10. high--;
11. if(lowhigh)
12. arr[low++] = arr[high];
13. while( lowhigh && arr[low]<>key )
14. low++;
15. if(lowhigh)
16. arr[high--] = arr[low];
17. }
18. arr[low] = key;
20. return low;
21. }
23. void quick_sort(int arr[], int start, int end){
24. int pos;
25. if (startend){
26. pos = partition(arr, start, end);
27. quick_sort(arr,start,pos-1);
28. quick_sort(arr,pos+1,end);
29. }
31. return;
32. }
34. int main(void){
35. int i;
36. int arr[N]={32,12,7, 78, 23,45};
38. printf('排序前 \n');
39. for(i=0;iN;i++)
40. printf('%d\t',arr[i]);
41. quick_sort(arr,0,N-1);
43. printf('\n 排序后 \n');
44. for(i=0; iN; i++)
45. printf('%d\t', arr[i]);
46. printf ('\n');
48. system('pause');
49. return 0;
50. }

運(yùn)行結(jié)果：

排序前32 12 7 78 23 45排序后7 12 23 32 45 78

在上面的代碼中,，根據(jù)前面介紹的步驟一步步實(shí)現(xiàn)了快速排序算法,。接下來通過示意圖來演示第一次劃分操作,。

在第一次劃分操作中，先進(jìn)行初始設(shè)置,，key的值是進(jìn)行劃分的基準(zhǔn)，其值為要?jiǎng)澐謹(jǐn)?shù) 組的第一個(gè)元素值,，在上面的排序序列中為第一個(gè)元素值32,，同時(shí)將low設(shè)置為要排序數(shù)組中第一個(gè)元素的下標(biāo)，第一次排序操作時(shí)其值為0,，將high設(shè)置為要排序序列最后一個(gè) 元素的下標(biāo),，在上面的排序序列中其第一次取值為5。先將下標(biāo)為high的數(shù)組元素與key進(jìn)行比較,，由于該元素值大于key,，因此high向左移動(dòng)一個(gè)位置繼續(xù)掃描。由于接下來的值為 23,，小于key的值,，因此將23賦值給下標(biāo)為low所指向的數(shù)組元素。接下來將low右移一 個(gè)位置,，將low所指向的數(shù)組元素的值與key進(jìn)行比較,，由干接下來的12、7都小于key,， 因此low繼續(xù)右移掃描,，直至下標(biāo)low所指向的數(shù)組元素的值為78即大于key為止，將78賦值給下標(biāo)為high所指向的數(shù)組元素,，同時(shí)將high左移一個(gè)位置,。接下來由于low不再小于high，劃分結(jié)束,。需要注意的是,，在進(jìn)行劃分的過程中，都是將掃描的值與key的值進(jìn)行對(duì)比,，如果小于key,，那么將該值賦值給數(shù)組中的另外一個(gè)元素，而該元素的值并沒有改變,。 從圖中可以看出這一點(diǎn),，所以需要在劃分的最后將作為劃分基準(zhǔn)的key值賦值給下標(biāo)為 pos的數(shù)組元素，這個(gè)元素不再參與接下來的劃分操作,。


第一次劃分操作
第一輪劃分結(jié)束后,，得到了左右兩部分序列A[0]、A[1],、A[2]和A[4],、A[5],，繼續(xù)進(jìn) 行劃分，即對(duì)毎輪劃分后得到的兩部分序列繼續(xù)劃分,，直至得到有序序列為止,。