星辰

版权声明：转载时请以超链接形式标明文章原始出处和作者信息及本声明
http://sundry.blogbus.com/logs/19704279.html

 快速排序法是由英国计算机科学家C.A.R.Hoare提出的，是一种比较有效的排序算法，平均时间复杂性为O(n log n)，比插入排序、冒泡排序和选择排序等方法的复杂性低，得到了非常广泛的应用。

快速排序法的思想：将要排序的向量按某种标准分为两个集合，再将每个集合 按该标准再 分为两个集合......以此类推（递归），当每个集合中只有一个数据时，排序完成。

程序的解释： Vector<T>& 是数组向量模板，low和high是向量要排序部分的上限和下限。

1.取最左边的数位参考值，比它大的向量都放在它右边，比他小的向量都放在它左边。模板函数如下 ：

template<class T>int partition(Vector<T>& vec,int low,int high){
 T pivot = vec[low];//参考值
 while(low<high){
  while(low<high&&vec[high]>pivot)
   high--;
  if(low<high){
   vec[low]=vec[high];
   low++;
  }
  while(low<high&&vec[low]<pivot)
   low++;
  if(low<high){
   vec[high]=vec[low];
   high--;
  }
 }
 vec[high]=pivot;
 return high;//返回值hign=low,也就是参考值现在所在的下标
}

2.实现递归

template<class T>void quickSort(Vector<T>& vec,int low,int high){
 if(low>=high)
  return;
 int m=partition(vec,low,high);//参考值的下标
 quickSort(vec,low,m-1);//调用自己 
 quickSort(vec,m+1,high);//调用自己

}

3.快速排序法的入口 ，重载了quickSort函数
template<class T>void quickSort(Vector<T>& vec){
 quickSort(vec,0,vec.getlenght()-1);
}

4.使用：

Vector<int> a(10);
a[0]=17;
a[1]=24;
a[2]=55;
a[3]=21;
a[4]=90;
a[5]=16;
a[6]=855;
a[7]=2;
a[8]=9;
a[9]=3;
quickSort(a);