快速排序是對冒泡排序的一種改進。它的基本思想是：通過一躺排序?qū)⒁判虻臄?shù)據(jù)分割成獨立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一不部分的所有數(shù)據(jù)都要小，然后再按次方法對這兩部分數(shù)據(jù)分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數(shù)據(jù)變成有序序列。
假設(shè)要排序的數(shù)組是A[1]……A[N]，首先任意選取一個數(shù)據(jù)（通常選用第一個數(shù)據(jù)）作為關(guān)鍵數(shù)據(jù)，然后將所有比它的數(shù)都放到它前面，所有比它大的數(shù)都放到它后面，這個過程稱為一躺快速排序。一躺快速排序的算法是：
1）、設(shè)置兩個變量I、J，排序開始的時候I：=1，J：=N；
2）以第一個數(shù)組元素作為關(guān)鍵數(shù)據(jù)，賦值給X，即X：=A[1]；
3）、從J開始向前搜索，即由后開始向前搜索（J：=J-1），找到第一個小于X的值，兩者交換；
4）、從I開始向后搜索，即由前開始向后搜索（I：=I+1），找到第一個大于X的值，兩者交換；
5）、重復(fù)第3、4步，直到I=J；
例如：待排序的數(shù)組A的值分別是：（初始關(guān)鍵數(shù)據(jù)X：=49）
A[1] A[2] A[3] A[4] A[5] A[6] A[7]：
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
( 按照算法的第五步將又一次執(zhí)行算法的第三步從后開始找
進行第四次交換后： 27 38 13 49 76 97 65
( 按照算法的第四步從前面開始找大于X的值，97>49,兩者交換，此時J：=4 )
此時再執(zhí)行第三不的時候就發(fā)現(xiàn)I=J，從而結(jié)束一躺快速排序，那么經(jīng)過一躺快速排序之后的結(jié)果是：27 38 13 49 76 97 65，即所以大于49的數(shù)全部在49的后面，所以小于49的數(shù)全部在49的前面。
快速排序就是遞歸調(diào)用此過程——在以49為中點分割這個數(shù)據(jù)序列，分別對前面一部分和后面一部分進行類似的快速排序，從而完成全部數(shù)據(jù)序列的快速排序，最后把此數(shù)據(jù)序列變成一個有序的序列，根據(jù)這種思想對于上述數(shù)組A的快速排序的全過程如圖6所示：
初始狀態(tài) {49 38 65 97 76 13 27}
進行一次快速排序之后劃分為 {27 38 13} 49 {76 97 65}
分別對前后兩部分進行快速排序 {13} 27 {38}
結(jié)束 結(jié)束 49 {65} 76 {97}
圖6 快速排序全過程
// QuickSort.cpp : Defines the entry point for the console application.//#include "stdafx.h"#include"stdio.h"void main()
...{
void quickSort(int [],int,int);
int a[7]=...{8,2,6,12,1,9,5};
int i; quickSort(a,0,6);/**//*排好序的結(jié)果*/ for(i=0;i<7;i++) printf("%4d",a[i]);}void quickSort(int a[],int left,int right)...{ int i,j,temp; i=left; j=right; temp=a[left]; if(left>right) return; while(i!=j)/**//*找到最終位置*/ ...{ while(a[j]>=temp && j>i) j--; if(j>i) a[i++]=a[j]; while(a[i]<=temp && j>i) i++; if(j>i) a[j--]=a[i]; } a[i]=temp; quickSort(a,left,i-1);/**//*遞歸左邊*/ quickSort(a,i+1,right);/**//*遞歸右邊*/}Trackback: http://tb.blog.csdn.net/TrackBack.aspx?PostId=1529686
