摘要:下面是希赛软考学院为大家提供的软考程序员教程重点提炼之快速排序算法,希望能帮助学友们。
下面是希赛软考网为大家提供的软考程序员教程重点提炼之快速排序算法,希望能帮助学友们。
代码:
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)。
希赛软考网,拥有十四年软考培训经验,希赛网一直坚持自主研发,将丰富的软考培训经验有效融入教程研发过程,自成体系的软考在线题库(软考历年真题)、软考培训教材和软考视频教程,多样的培训方式包括在线辅导、面授、和,使考生的学习更具系统性,辅导更具针对性。采用全程督学机制,,软考平均通过率在全国。
软考备考资料免费领取
去领取