公司不發(fā)工資了。。。。
快速排序算法是基于分治算法的一種排序。主要思想分成兩步（從小到大排序）：
（1）分解，取出排序數(shù)列中一個(gè)數(shù)字，將數(shù)分成三段，左邊段數(shù)列數(shù)值大于等于取出數(shù)，右邊段數(shù)列值小于等于取出數(shù)，中間是取出數(shù)；
（2）遞歸求解；
第一步其實(shí)是根據(jù)分治算法的基本思想，將一個(gè)規(guī)模為n的問題分成3個(gè)規(guī)模較小的問題，其中規(guī)模為1的在這次運(yùn)算后，就是最后結(jié)果中的位置了；
第二步其實(shí)是將規(guī)模較小的另兩個(gè)數(shù)列，繼續(xù)分解下去，其中每一次分解都會(huì)確定一個(gè)數(shù)在最后結(jié)果中的位置，
在這樣的思想下，該程序設(shè)計(jì)最關(guān)鍵的一種操作就是怎樣把數(shù)組分解成左邊段數(shù)列數(shù)值大于等于取出數(shù)，右邊段數(shù)列值小于等于取出數(shù)；
書上的代碼如下：
#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]; //因?yàn)槿〉谝粋€(gè)數(shù)為參考值
while(1) //死循環(huán)
{
while(a[++i]<x&&i<r); //一個(gè)從左邊找比x大的數(shù)
while(a[--j]>x); //一個(gè)從右邊找比x小的數(shù)
if(i>=j) //死循環(huán)跳出條件，為什么是i>=j呢？i>=j意味著j左邊數(shù)列值都小于x（包括j），右邊數(shù)列值都大于x了！
break;
Swap(a[i],a[j]); //沒跳出死循環(huán)，就應(yīng)該交換
}
a[p]=a[j];
a[j]=x; //交換p與j位置上的值，因?yàn)閍[j]<=x！！到這里p位置上的數(shù)，位置就確定下來了！
return j; //返回位置值，為另兩端提供參數(shù)！
}
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]是數(shù)列最小值，Partition(a,p,r)返回p，a[p]值不變！我測(cè)試了一下，是期望結(jié)果。。。
網(wǎng)上還有快速排序視屏，巨好玩！http://v.youku.com/v_show/id_XMTg1MjIwMDY0.html
posted on 2010-09-01 16:14
jince 閱讀(404)
評(píng)論(1) 編輯 收藏 引用 所屬分類:
算法設(shè)計(jì)與分析