快速排序.txt.txt

从数组中 任取一个元素 p (可随机取,现在以取第一个为例).以P作为主元,对数组 进行划分 ,前一部分小于 P,后一部分 大于p.最后划分处存储p,然后分别对划分后的前一部分和后一部分递归调用.

快速排序
void QuickSort(int low,int high,int *array)
{
int pos;
if(low<high)
{
  pos=SPLIT(low,high,array);     //以array[low]进行划分,pos最为划分点
             //前一部分<array[low],后一部分,反之
  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<high)
{
  while(array[high]>temp&&low<high)      //寻找小于temp的数
   high--;
  if(low==high)
   break;
  else
  {
   array[low]=array[high];     
   low++;
  }
  while(array[low]<temp&&low<high)   //寻找大于temp的数
   low++;
  if(low==high)
   break;
  else
  {
   array[high]=array[low];
   high--;
  }
}
array[low]=temp;        //最终low=high作为划分点,并将划分数存于array[low]
return low;
}