公司不發工資了。。。。
快速排序算法是基于分治算法的一種排序。主要思想分成兩步（從小到大排序）：
（1）分解，取出排序數列中一個數字，將數分成三段，左邊段數列數值大于等于取出數，右邊段數列值小于等于取出數，中間是取出數；
（2）遞歸求解；
第一步其實是根據分治算法的基本思想，將一個規模為n的問題分成3個規模較小的問題，其中規模為1的在這次運算后，就是最后結果中的位置了；
第二步其實是將規模較小的另兩個數列，繼續分解下去，其中每一次分解都會確定一個數在最后結果中的位置，
在這樣的思想下，該程序設計最關鍵的一種操作就是怎樣把數組分解成左邊段數列數值大于等于取出數，右邊段數列值小于等于取出數；
書上的代碼如下：
#include<iostream>
#include<algorithm>
using namespace std;
template <class Type>
void QuickSort(Type a[],int p,int r)
{
if(p<r)
{
int q=Partition(a,p,r); //分解
QuickSort(a,p,q-1); //左半段排序
QuickSort(a,q+1,r); //有半段排序
}
}
void Swap(int &a,int &b) //交換
{
int c;
c=a;
a=b;
b=c;
}
int Partition(int a[],int p,int r) //分解
{
int i=p,j=r+1; //為啥i=p,j=r+1呢？
int x=a[p]; //因為取第一個數為參考值
while(1) //死循環
{
while(a[++i]<x&&i<r); //一個從左邊找比x大的數
while(a[--j]>x); //一個從右邊找比x小的數
if(i>=j) //死循環跳出條件，為什么是i>=j呢？i>=j意味著j左邊數列值都小于x（包括j），右邊數列值都大于x了！
break;
Swap(a[i],a[j]); //沒跳出死循環，就應該交換
}
a[p]=a[j];
a[j]=x; //交換p與j位置上的值，因為a[j]<=x！！到這里p位置上的數，位置就確定下來了！
return j; //返回位置值，為另兩端提供參數！
}
int main()
{
int i;
int a[10]={3,4,5,3,2,5,6,8,9,2};
for(i=0;i<10;i++)
printf("%d ",a[i]);
printf("\n");
QuickSort(a,0,9);
for(i=0;i<10;i++)
printf("%d ",a[i]);
printf("\n");
return 0;
}
特殊情況下：如果選取的a[p]是數列最小值，Partition(a,p,r)返回p，a[p]值不變！我測試了一下，是期望結果。。。
網上還有快速排序視屏，巨好玩！http://v.youku.com/v_show/id_XMTg1MjIwMDY0.html
posted on 2010-09-01 16:14
jince 閱讀(415)
評論(1) 編輯 收藏 引用 所屬分類:
算法設計與分析