如何优化快速排序算法
RT
书上说到优化快速排序是修改“一次划分”算法，在指针high减1和low增1的同时进行冒泡操作，同时附设两个布尔型变量分别指示low和high在从两端向中间的移动过程中是否进行过交换记录的操作，若low从低端向中间的移动过程中没有进行交换记录的操作，则不再需要对低端子表进行排序，类似high指针也是如此。
这样划分可以进一步改善快速排序的平均性能。
对书上的说明不太明白 希望有人可以解释下 有算法或代码说明更好 谢谢
问题点数：100、回复次数：8Top
1 楼ugg（逸学堂(exuetang.net)）回复于 2006-03-31 13:01:15 得分 1
一向对算法缺乏研究。
帮你upTop
2 楼ChenSu2008（北海沉书）回复于 2006-03-31 13:13:52 得分 27
template <class Type>
void QuickSort ( datalist<Type> &list, const int left, const int right ) {
//在待排序区间 leftright 中递归地进行快速排序
if ( left < right) {
int pivotpos = Partition ( list, left, right ); //划分
//在左子区间递归进行快速排序
QuickSort ( list, left, pivotpos-1);
//在右子区间递归进行快速排序
QuickSort ( list, pivotpos+1, right );
}
}
template <class Type>
int Partition ( datalist<Type> &list, const int low,
const int high ) {
int pivotpos = low; //基准位置
Element<Type> pivot = list.Vector[low];
for ( int i = low+1; i <= high; i++ )
if ( list.Vector[i].getKey ( ) < pivot.getKey( ) && ++pivotpos != i )
Swap( list.Vector[pivotpos], list.Vector[i] );
//小于基准对象的交换到区间的左侧去
Swap ( list.Vector[low], list.Vector[pivotpos] );
return pivotpos;
}
"在指针high减1和low增1的同时进行冒泡操作"
这个不太明白，但是对于后面那点，这个算法已经这样做了。
[来源于清华大学-数据结构\C++ 描述]Top
3 楼yuanchuang（元创）回复于 2006-03-31 13:48:54 得分 1
我也帮你UPTop
4 楼cyberHunK（→迈克·老猫←）回复于 2006-03-31 14:37:36 得分 50
首先要了解快速排序的缺点，在无序数据中，快速排序有很好的效果。但在对于数据存在有序、反向有序及主次有序的形态时，快速排序都存在引起退化到二次行为的严重缺陷！
由于这个缺点，你的这个改进算法是在排序的前期进行了数据有序与否的检查，尽量缩短数据交换的次数！而快速排序一种真正的改进算法是单个排序，算法思想如下：(以一把硬币为例)
1、把硬币倒成一堆；
2、检查硬币堆是否已经有序；如果无序，则：
3、搅拌硬币并从硬币堆中抓取一些硬币。挑出这批硬币中的中值硬币；
4、把面值更大的硬币放在右边的硬币堆；
5、把面值更小的硬币放在左边的硬币堆；
6、如果硬币对很小，使用折半插入算法，否则：
7、对于每一堆硬币，返回步骤2，直到所有硬币全部排序完毕。由于把大面值硬币放在右边，而把小面值硬币放在左边，因而当每堆只有一枚硬币时，所有硬币完全有序。
Top
5 楼hbyufan（）回复于 2006-04-01 05:19:21 得分 10
提供几个网子去看看，帮顶
http://www.stlchina.org/twiki/bin/view.pl/Main/STLSortAlgorithms
http://www.gd-emb.org/detail/id-2233.html
http://edu.yesky.com/edupxpt/42/2072542.shtmlTop
6 楼wuyinggu（寂寞小阳春）回复于 2006-04-01 23:40:20 得分 10
这是一个快速排序的程序：
#include<stdio.h>
void quick_sort(int array[],int first,int last)//first,last分别为数组下标的范围；
{
int temp,low,high,list_separator;
low=first;
high=last;
/*下面是比较数组中的大小，把数组中的数与中间数比较，大的放在后半部分，比中间数小的放在前半部分，*/
list_separator=array[(first+last)/2];//中间数；
do{
while(array[low]<list_separator)//中间数与前半部分比较；
low++;
while(array[high]>list_separator)// 中间数与后半部分比较；
high--;
if(low<=high)//前半部分与后半部分交换；
{
temp=array[low];
array[low++]=array[high];
array[high--]=temp;
}
}while(low<=high);
if(first<high)
quick_sort(array,first,high);//利用递归的办法，实行循环；
if(low<last)
quick_sort(array,low,last);//利用递归的办法，实行循环；
} 请高手优化！！！
Top
7 楼skywoody（）回复于 2006-04-02 00:59:36 得分 1
直接用STL的sort多好啊
效率比自己写的快排好多了而且可靠Top
8 楼ox_thedarkness（）回复于 2006-04-02 01:18:41 得分 0
回楼上的，如果要考试那么还是得自己做...Top
