|
快速排序是對冒泡排序的一種改進。它的基本思想是：通過一趟排序將要排序的數據分割成獨立的兩部分，其中一部分的所有數據都比另外一部分的所有數據都要小，然后再按次方法對這兩部分數據分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數據變成有序序列。
假設要排序的數組是A[1]……A[N]，首先任意選取一個數據（通常選用第一個數據）作為關鍵數據，然后將所有比它的數都放到它前面，所有比它大的數都放到它后面，這個過程稱為一趟快速排序。一趟快速排序的算法是：
1）設置兩個變量I、J，排序開始的時候 I=0，J=N-1；
2）以第一個數組元素作為關鍵數據，賦值給X，即X=A[0]；
3）從J開始向前搜索，即由后開始向前搜索，找到第一個小于X的值，兩者交換；
4）從I開始向后搜索，即由前開始向后搜索，找到第一個大于X的值，兩者交換；
5）重復第3、4步，直到I=J；
例如：待排序的數組A的值分別是：（初始關鍵數據X：=49）
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}
分別對前后兩部分進行快速排序 {13} 27 {38}
結束 結束 {49 65} 76 {97}
49 {65} 結束
結束
--------------------- 參考代碼 -------------------------
- void quiksort(int a[],int low,int high)
- {
- int i = low;
- int j = high;
- int temp = a[i];
-
- if( low < high)
- {
- while(i < j)
- {
- while((a[j] >= temp) && (i < j))
- {
- j--;
- }
- a[i] = a[j];
- while((a[i] <= temp) && (i < j))
- {
- i++;
- }
- a[j]= a[i];
- }
- a[i] = temp;
- quiksort(a,low,i-1);
- quiksort(a,j+1,high);
- }
- else
- {
- return;
- }
- }
-
- void main()
- {
- int arry[5] = {23,1,21,4,19};
- quiksort(arry,0,4);
- for(i=0;i<5;i++)
- {
- printf("%d ",arr[i]);
- }
- printf("\n");
- }
| 
