快速排序是對冒泡排序的一種改進。它的基本思想是：通過一躺排序?qū)⒁判虻臄?shù)據(jù)分割成獨立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一不部分的所有數(shù)據(jù)都要小，然后再按次方法對這兩部分數(shù)據(jù)分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數(shù)據(jù)變成有序序列。
假設要排序的數(shù)組是A[1]……A[N]，首先任意選取一個數(shù)據(jù)（通常選用第一個數(shù)據(jù)）作為關鍵數(shù)據(jù)，然后將所有比它的數(shù)都放到它前面，所有比它大的數(shù)都放到它后面，這個過程稱為一躺快速排序。一躺快速排序的算法是：
1）、設置兩個變量I、J，排序開始的時候I：=1，J：=N；
2）以第一個數(shù)組元素作為關鍵數(shù)據(jù)，賦值給X，即X：=A[1]；
3）、從J開始向前搜索，即由后開始向前搜索（J：=J-1），找到第一個小于X的值，兩者交換；
4）、從I開始向后搜索，即由前開始向后搜索（I：=I+1），找到第一個大于X的值，兩者交換；
5）、重復第3、4步，直到I=J；
例如：待排序的數(shù)組A的值分別是：（初始關鍵數(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，從而結束一躺快速排序，那么經(jīng)過一躺快速排序之后的結果是：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}
結束 結束 {49 65} 76 {97}
49 {65} 結束
結束
圖6 快速排序全過程
1）、設有N（假設N=10）個數(shù)，存放在S數(shù)組中；
2）、在S[1。。N]中任取一個元素作為比較基準，例如取T=S[1]，起目的就是在定出T應在排序結果中的位置K，這個K的位置在：S[1。。K-1]<=S[K]<=S[K+1..N]，即在S[K]以前的數(shù)都小于S[K]，在S[K]以后的數(shù)都大于S[K]；
3）、利用分治思想（即大化小的策略）可進一步對S[1。。K-1]和S[K+1。。N]兩組數(shù)據(jù)再進行快速排序直到分組對象只有一個數(shù)據(jù)為止。
如具體數(shù)據(jù)如下，那么第一躺快速排序的過程是：
數(shù)組下標： 1 2 3 4 5 6 7 8 9 10
45 36 18 53 72 30 48 93 15 36
I J
（1） 36 36 18 53 72 30 48 93 15 45
（2） 36 36 18 45 72 30 48 93 15 53
（3） 36 36 18 15 72 30 48 93 45 53
（4） 36 36 18 15 45 30 48 93 72 53
（5） 36 36 18 15 30 45 48 93 72 53
通過一躺排序?qū)?5放到應該放的位置K，這里K=6，那么再對S[1。。5]和S[6。。10]分別進行快速排序。
一般來說，冒泡法是程序員最先接觸的排序方法，它的優(yōu)點是原理簡單，編程實現(xiàn)容易，但它的缺點就是--程序的大忌--速度太慢。下面我介紹一個理解上簡單但編程實現(xiàn)上不是太容易的排序方法，我不知道它是不是現(xiàn)有排序方法中最快的，但它是我見過的最快的。排序同樣的數(shù)組，它所需的時間只有冒泡法的 4% 左右。我暫時稱它為“快速排序法”。
“快速排序法”使用的是遞歸原理，下面我結合一個例子來說明“快速排序法”的原理。首先給出一個數(shù)組{53，12，98，63，18，72，80，46， 32，21}，先找到第一個數(shù)--53，把它作為中間值，也就是說，要把53放在一個位置，使得它左邊的值比它小，右邊的值比它大。{21，12，32， 46，18，53，80，72，63，98}，這樣一個數(shù)組的排序就變成了兩個小數(shù)組的排序--53左邊的數(shù)組和53右邊的數(shù)組，而這兩個數(shù)組繼續(xù)用同樣的方式繼續(xù)下去，一直到順序完全正確。
我這樣講你們是不是很胡涂，不要緊，我下面給出實現(xiàn)的兩個函數(shù)：
/*
n就是需要排序的數(shù)組，left和right是你需要排序的左界和右界，
如果要排序上面那個數(shù)組，那么left和right分別是0和9
*/
void quicksort(int n[], int left,int right)
{
int dp;
if (left<right) {
/*
這就是下面要講到的函數(shù)，按照上面所說的，就是把所有小于53的數(shù)放
到它的左邊，大的放在右邊，然后返回53在整理過的數(shù)組中的位置。
*/
dp=partition(n,left,right);
quicksort(n,left,dp-1);
quicksort(n,dp+1,right); //這兩個就是遞歸調(diào)用，分別整理53左邊的數(shù)組和右邊的數(shù)組
}
}
我們上面提到先定位第一個數(shù)，然后整理這個數(shù)組，把比這個數(shù)小的放到它的左邊，大的放右邊，然后
返回這中間值的位置，下面這函數(shù)就是做這個的。
int partition(int n[],int left,int right)
{
int lo,hi,pivot,t;
pivot=n[left];
lo=left-1;
hi=right+1;
while(lo+1!=hi) {
if(n[lo+1]<=pivot)
lo++;
else if(n[hi-1]>pivot)
hi--;
else {
t=n[lo+1];
n[++lo]=n[hi-1];
n[--hi]=t;
}
}
n[left]=n[lo];
n[lo]=pivot;
return lo;
}
posted on 2009-11-17 18:29
鵬凌 閱讀(2087)
評論(0) 編輯 收藏 所屬分類:
Java --j2ee