13
回答
“快速排序“ 的一个疑问,请教下各位朋友:)
利用AWS快速构建适用于生产的无服务器应用程序,免费试用12个月>>>   

quicksort在序列的各个元素不相同时效率比较高, nlgn。

但是,如果序列的各个元素几乎都相同时,效率就低了,n^2。

以下是我对randomized quicksort的一个测试

./quicksort [size] [range] 表示 sort [size] elements of range [0 - range]

~/MyPro/Algorithms/sort $ ./quicksort 1024 10000000
start sorting ...
sorting finished!
====================================
Randomized Quicksort               
Sorting 1024 elements
Time: 0s      468us
The result is right !
====================================


~/MyPro/Algorithms/sort $ ./quicksort 1024 1
start sorting ...
sorting finished!
====================================
Randomized Quicksort               
Sorting 1024 elements
Time: 0s      15426us
The result is right !
====================================

可以看到,当元素几乎相同时(如第二个输入,元素只有0和1),排序效率明显很低。

有么有什么办法对quicksort进行改进使它可以处理这种情况呢?

举报
ChenQi
发帖于6年前 13回/532阅
共有13个答案 最后回答: 6年前

这个事情不能强求的。抽象点将,你使用一个中优化方式,是有边界条件的。当在边界条件的另一端的实例,就会导致你做的更差。

关键看你是想用非等概率的优化策略,还是等概率的优化策略。后者也有。只不过任意数据进来,时间都差不多。而不会这个样本快,那个样本慢这种情况出现。

看你对输入数据的先验的假设情况了。

time1= now

xxx

...

xxx

time2=now

time= time2-time1

然后说怎么优化呢?

这都跟谁学的啊?!!!!!!!!!!!误人子弟啊!

--- 共有 1 条评论 ---
ChenQi额。。。。我对优化没什么了解。我这种计时方法不太对么?我在两次取时间之间,只调用了quicksort这个排序。 6年前 回复

引用来自“中山野鬼”的答案

这个事情不能强求的。抽象点将,你使用一个中优化方式,是有边界条件的。当在边界条件的另一端的实例,就会导致你做的更差。

关键看你是想用非等概率的优化策略,还是等概率的优化策略。后者也有。只不过任意数据进来,时间都差不多。而不会这个样本快,那个样本慢这种情况出现。

看你对输入数据的先验的假设情况了。

比如,我想要的结果是无论什么序列进来,其运行时间最多只在nlgn数量级,怎么做呢?

n^2的运行时间实在太长了。如果size再大一点,可能半天出不来结果,所以,如果有办法能使所有输入都在nlgn运行初来就好了,即使平均下来比较慢也没关系。(另外,输入不一定是整数,可能是浮点数。不要用非比较模型的排序算法。)

 

--- 共有 2 条评论 ---
周翼翼回复 @中山野鬼 : 非比较模型就是不是直接比较按键值大小来决定位置的, 我记得是这样. 比较模型总要if(a>b)之类的东西. 我还记得,比较模型排序撑死了最好的复杂度是O(nlog), 这是在数学上证明了的, 你不是搞数学嘛, 来来来, 求证. 6年前 回复
中山野鬼什么叫做非比较模型?排序算法固定下,唯一不定是对比较的方式的差异性。你改成浮点比较,还有什么问题? 6年前 回复
数量级O(nlogn)的排序算法有现成的啊,insert-sort-with-binary-search,inplace-merge-sort,heap-sort都是雷打不动的O(nlogn),不论输入的是什么样的数据。
--- 共有 1 条评论 ---
中山野鬼楼主,这有答案了。。。哈。 6年前 回复

引用来自“liuex”的答案

数量级O(nlogn)的排序算法有现成的啊,insert-sort-with-binary-search,inplace-merge-sort,heap-sort都是雷打不动的O(nlogn),不论输入的是什么样的数据。

确实。

但是,我想要的效果是:对quicksort进行微调达到能处理大量重复数据的排序的效果。

起因是我看到书上说,quicksort是应用最广泛也是最实用的排序之一,对quicksort进行各种微调,能使得它应用于各种实际情况(比如对小序列进行其他排序算法)。然后,我就想到如果输入数据大量重复会如何?故有此一问。

--- 共有 3 条评论 ---
Lunar_Lin或者你就用堆排序吧.堆排序速度也是非常快的,它和快排也是在百万级的数据时才拉开距离.但它效率就非常的稳定. 6年前 回复
Lunar_Lin不只是数字重复率高, 在数据已经排好序的情况下,快排也是非常慢的.不过后者有克服的办法, 但重复率高我觉得无法克服. 6年前 回复
Lunar_Lin 综合的看,快速排序只是在普通时候最快而已.你的情况已经不是普通时候了,那么还想最快的话,就不应该使用这种方法. 6年前 回复

引用来自“ChenQi”的答案

引用来自“liuex”的答案

数量级O(nlogn)的排序算法有现成的啊,insert-sort-with-binary-search,inplace-merge-sort,heap-sort都是雷打不动的O(nlogn),不论输入的是什么样的数据。

确实。

但是,我想要的效果是:对quicksort进行微调达到能处理大量重复数据的排序的效果。

起因是我看到书上说,quicksort是应用最广泛也是最实用的排序之一,对quicksort进行各种微调,能使得它应用于各种实际情况(比如对小序列进行其他排序算法)。然后,我就想到如果输入数据大量重复会如何?故有此一问。

哈。输入数据大量重复。这是个好题目。首先,要明确,我说的只试用定点。记得,浮点的玩意头,不要用 == 比较。在浮点加减乘除后。

那么大量重复的数据我就不写代码了。比较浪费时间。如果你调试半天调试不通的话,我会帮你写一下。

先回顾一下快速算法。基本思想两个。

1、当前序列,已知 left ,right,任取一个值作为基准值,大于的放右边,小于的放左边。

2、将上述该基准值(移动后的位置)假设为 r_pos,则 left 到 r_pos - 1, r_pos+1和right重复1的工作。

那么你的大量相等数据的调整策略就是如下

1、当前序列,已知left ,right,任取一个值作为基准带里的元素,初始化基准带就是一个。我们对基准带标记为 r_pos_r(ref_pos_right) ,r_pos_l,大于的放右边,小于的放左边。等于的则扩充基准带继续处理。

2、对上述基准带则, left 到 r_pos_l - 1的,和r_pos_r +1 到right重复 1的工作。

今天太晚了。我就不上代码了。明天有空,你调试不出来,我给你写个代码。你看一下。但是基于你把你写的代码先列出来。

 

算了,不折腾完,没心情休息。下面我把代码给你。基本没错。但是用的是伪代码方式,就是递归方式。正常需要非递归方式实现。
void quicksort2(int *p,int length){
     int ref_pos_l = 0;
     int ref_pos_r = 0;
     int ref_data = p[ref_pos_l];
     int j = length;

     while (j > ref_pos_r){ //the while only p[j] < ref_data ,break
       	while (p[j] > ref_data && j > ref_pos_r){ j--;} //only > ,mov point j by right to left ,continue
       	if (j <= ref_pos_r){
       		break;
       	}
       	if (p[j] == ref_data){
       		//we find one compared data equ ref_data ,
       		p[j] = p[++ref_pos_r];//the ref windows spread,and change the new data into p[j]
            p[ref_pos_r] = ref_data; //we need push this gay into ref window,and adjust
       	}else{         	
       		//found one small data
       		p[ref_pos_l++] = p[j];//push small data into left 
       		p[j] = p[ref_pos_r+1]; // change the new data into p[j]
       		p[++ref_pos_r] = ref_data; //mov the ref window by left to right , i used ref_pos_l++ ,ref_pos_r++
       	}
    }
    p[ref_pos_r] = ref_data;
    if(ref_pos_l - 1 > 0){
         quicksort2(p, ref_pos_l-1);
    }
    if(ref_pos_r +1 < length){
         quicksort2(p+ref_pos_r+1, length-ref_pos_r-1);
    } 
     
}

对了,不是我装B,我可不想遭雷劈。只是我不太习惯在代码里面写中文。有时转环境全是乱码。所以你得忍受我的弱智英语。这样可以保证你的重复相等的数据不参与下一轮的计算。

如果是给我自己看的代码,注释就只有一条,其他都不会存在。如下

void quicksort2(int *p,int length){
//WARING!!!NOT TO BE USED 。THIS IS RECURSION

我还是那句话,傻逼用递归,我不怕被人喷。

--- 共有 1 条评论 ---
ChenQi辛苦了。3q 6年前 回复

if(数据大,且重复率高)  //这处判断的耗时 可能就让你的优化白费.
     use_heap_sort();
else
    use_quick_sort();

--- 共有 6 条评论 ---
中山野鬼回复 @Lunar_Lin : 都是应该小朋友做的题目。我是闲得蛋疼,顺顺手而已。 6年前 回复
Lunar_Lin回复 @中山野鬼 : 是的.所以快排用在这种特殊的情况下比较头疼.你的改良不错. 6年前 回复
中山野鬼回复 @Lunar_Lin : 有个问题哦。如何通过一次扫描解决,如下问题。假设N个数大于100个,其中相同的只有1和2,但存在两种可能,存在5个1和5个2,与存在 7个与 3个2的差异?一次扫描只能对第一层递归有效。对子递归,是无法利用该信息的。不知道你是否考虑过。 6年前 回复
Lunar_Lin回复 @ChenQi : http://www.cnblogs.com/kkun/archive/2011/11/23/2260312.html 6年前 回复
Lunar_Lin这个判断肯定是要O(n)的复杂度.每次运算都加入这样的判断是很有害的. 建议事先判断出场景,无法预先判断的,就完全放弃快排.这个链接可以作为你的参考,非百万级以上,是看不出快排有多快的. 我想很少有软件会有一次性进行百万级排序的设计吧? http://commons.wikimedia.org/wiki/File:SortingAlgoComp.png 6年前 回复

先判数据的场景啊,如果是大量重复最好就不要用快速排序了

快速排序不是稳定的,对于大量重复的数据还是用稳定的排序算法好,比如说堆排序,归并排序,shell排序,虽然比快速排序慢一点,但至少是稳定的

引用来自“中山野鬼”的答案

算了,不折腾完,没心情休息。下面我把代码给你。基本没错。但是用的是伪代码方式,就是递归方式。正常需要非递归方式实现。
void quicksort2(int *p,int length){
     int ref_pos_l = 0;
     int ref_pos_r = 0;
     int ref_data = p[ref_pos_l];
     int j = length;

     while (j > ref_pos_r){ //the while only p[j] < ref_data ,break
       	while (p[j] > ref_data && j > ref_pos_r){ j--;} //only > ,mov point j by right to left ,continue
       	if (j <= ref_pos_r){
       		break;
       	}
       	if (p[j] == ref_data){
       		//we find one compared data equ ref_data ,
       		p[j] = p[++ref_pos_r];//the ref windows spread,and change the new data into p[j]
            p[ref_pos_r] = ref_data; //we need push this gay into ref window,and adjust
       	}else{         	
       		//found one small data
       		p[ref_pos_l++] = p[j];//push small data into left 
       		p[j] = p[ref_pos_r+1]; // change the new data into p[j]
       		p[++ref_pos_r] = ref_data; //mov the ref window by left to right , i used ref_pos_l++ ,ref_pos_r++
       	}
    }
    p[ref_pos_r] = ref_data;
    if(ref_pos_l - 1 > 0){
         quicksort2(p, ref_pos_l-1);
    }
    if(ref_pos_r +1 < length){
         quicksort2(p+ref_pos_r+1, length-ref_pos_r-1);
    } 
     
}

对了,不是我装B,我可不想遭雷劈。只是我不太习惯在代码里面写中文。有时转环境全是乱码。所以你得忍受我的弱智英语。这样可以保证你的重复相等的数据不参与下一轮的计算。

如果是给我自己看的代码,注释就只有一条,其他都不会存在。如下

void quicksort2(int *p,int length){
//WARING!!!NOT TO BE USED 。THIS IS RECURSION

我还是那句话,傻逼用递归,我不怕被人喷。

@非也 其实我早年仔细比对了 基数MSD LSD排序  发现其实在64位机器下 使用递归比不适用快  但是有硬件问题  我当时就好奇JDK是怎么判断深度溢出的 后来进去看JDK的qsort 原来加上了一句deep<7 then mergesort()... 后来JDK又加上了传说中的排序之神tim-peter排序  JDK的排序就基本上天下无敌了 绝对比STL快! 但是...他的确用到了递归和硬编码防止溢出  不信你去看64位JDK 就不是<7 .... PS Tim Peter 真神人也
--- 共有 2 条评论 ---
圣何塞白话人code google 6年前 回复
Lunar_Lin没找到Tim peter排序算法资料. 6年前 回复
顶部