职业教育新东方网 > 职业教育 > 计算机 > 软件考试 > 初级资格 > 程序员 > 文章正文

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

分享到:

2011-10-28 09:20  作者:  来源:互联网  字号:T|T

  代码:

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

(责任编辑:单月)

 

热点课讯

精彩问答

提问