|
快速排序是對(duì)冒泡排序的一種改進(jìn)。它的基本思想是：通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按次方法對(duì)這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序，整個(gè)排序過程可以遞歸進(jìn)行，以此達(dá)到整個(gè)數(shù)據(jù)變成有序序列。
假設(shè)要排序的數(shù)組是A[1]……A[N]，首先任意選取一個(gè)數(shù)據(jù)（通常選用第一個(gè)數(shù)據(jù)）作為關(guān)鍵數(shù)據(jù)，然后將所有比它的數(shù)都放到它前面，所有比它大的數(shù)都放到它后面，這個(gè)過程稱為一趟快速排序。一趟快速排序的算法是：
1）設(shè)置兩個(gè)變量I、J，排序開始的時(shí)候 I=0，J=N-1；
2）以第一個(gè)數(shù)組元素作為關(guān)鍵數(shù)據(jù)，賦值給X，即X=A[0]；
3）從J開始向前搜索，即由后開始向前搜索，找到第一個(gè)小于X的值，兩者交換；
4）從I開始向后搜索，即由前開始向后搜索，找到第一個(gè)大于X的值，兩者交換；
5）重復(fù)第3、4步，直到I=J；
例如：待排序的數(shù)組A的值分別是：（初始關(guān)鍵數(shù)據(jù)X：=49）
A[0] A[1] A[2] A[3] A[4] A[5] A[6]
49 38 65 97 76 13 27
進(jìn)行第一次交換后： 27 38 65 97 76 13 49
( 按照算法的第三步從后面開始找 ）
進(jìn)行第二次交換后： 27 38 49 97 76 13 65
( 按照算法的第四步從前面開始找>X的值，65>49,兩者交換，此時(shí)I=3 )
進(jìn)行第三次交換后： 27 38 13 97 76 49 65
( 按照算法的第五步將又一次執(zhí)行算法的第三步從后開始找）
進(jìn)行第四次交換后： 27 38 13 49 76 97 65
( 按照算法的第四步從前面開始找大于X的值，97>49,兩者交換，此時(shí)J=4 )
此時(shí)再執(zhí)行第三不的時(shí)候就發(fā)現(xiàn)I=J，從而結(jié)束一躺快速排序，那么經(jīng)過一躺快速排序之后：
27 38 13 49 76 97 65 即所有大于49的數(shù)全部在49的后面，所有小于49的數(shù)全部在49的前面。
快速排序就是遞歸調(diào)用此過程——在以49為中點(diǎn)分割這個(gè)數(shù)據(jù)序列，分別對(duì)前面一部分和后面一部分進(jìn)行類似的快速排序，從而完成全部數(shù)據(jù)序列的快速排序，最后把此數(shù)據(jù)序列變成一個(gè)有序的序列，根據(jù)這種思想對(duì)于上述數(shù)組A的快速排序的全過程如圖6所示：
初始狀態(tài) {49 38 65 97 76 13 27}
進(jìn)行一次快速排序之后劃分為 {27 38 13} 49 {76 97 65}
分別對(duì)前后兩部分進(jìn)行快速排序 {13} 27 {38}
結(jié)束 結(jié)束 {49 65} 76 {97}
49 {65} 結(jié)束
結(jié)束
--------------------- 參考代碼 -------------------------
- 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");
- }
| 
QQ好友和群
QQ空間
騰訊微博
騰訊朋友
收藏
淘帖
頂
踩
