公司不发工资了。。。。
快速排序算法是基于分治算法的一种排序。主要思想分成两步（从小到大排序）：
（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 阅读(372)
评论(1) 编辑 收藏 引用 所属分类:
算法设计与分析