中部培训网 > 培训新闻 > 电脑 > 软件开发 > > 软件工程师 - 正文

2012年软考程序员算法实例:快速排序算法

2012-03-27 16:30:15

代码:

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)。

相关新闻