2015年软考程序员算法实例：快速排序算法
发布时间：2011/3/18 10:49:19 来源：城市学习网 编辑：ziteng
代码：
void QuickSort(int low,int high,int *array)
{
int pos;
if(low{
pos=SPLIT(low,high,array); //以array[low]进行划分,pos最为划分点
//前一部分后一部分,反之
QuickSort(low,pos-1,array); //对划分后的前一部分递归处理
QuickSort(pos+1,high,array); //对划分后的后一部分递归处理
}
}
int SPLIT(int low,int high,int *array)
{
int temp=array[low]; //用temp来记录划分数
while(low{
while(array[high]>temp&&low寻找小于temp的数
high--;
if(low==high)
break;
else
{
array[low]=array[high];
low++;
}
while(array[low]寻找大于temp的数
low++;
if(low==high)
break;
else
{
array[high]=array[low];
high--;
}
}
array[low]=temp; //最终low=high作为划分点,并将划分数存于array[low]
return low;
}
思想：
就是你从数组中任取一个元素p(可随机取,现在以取第一个为例);
以P作为主元,对数组 进行划分 ,前一部分小于 P,后一部分大于p;
最后划分处存储 p;
然后分别对划分后的前一部分和后一部分递归调用;
算法平均时间复杂度: O(nlogn)。
