Chinaunix

标题: Quick Sort 的一个注记 [打印本页]
作者: win_hate    时间: 2007-11-04 18:21
标题: Quick Sort 的一个注记
这是我 blog 上新发的一个随笔--- 一个“学而不思则惘”的故事。


前天参加一个讨论班，报告者在讲 Quick Sort 时，精力全集中在分割算法上了。他说：“你们一定要多体会一下，这个算法是先跟这边比，再跟那边比，又跟这边比，再跟那边比，如是直到相会。不这样的话，将无法理解 Quick Sort.

对这个说法我很不同意。当然线性时间的分割算法是 Quick Sort 最出彩，最有技巧的地方，但 Quick Sort 的 big idea 并不在这里。从大方向上看，Quick Sort 都干了什么？

    * 找一个枢纽元 p ，把数组分成两部分，左边的比 p 小，右边的比 p 大。
    * 找一个元素 r, 把数组分成两部分，比 r 小的作为子树接在 r 的左边，比 r 大的最为子树接在树的右边。

不难看出，Quick Sort 其实在建一棵二叉排序树，这是它跟其它排序算法最不同的地方。其它几种常见的排序算法都专注于如何排出一个按序的线性序列，Quick Sort 表面上也如此，但背后却藏了一棵二叉树。这也能说明为什么原始的 Quick Sort 会有一个 O(n^2) 的最坏情形，此时对应的二叉树一定非常不平衡(比如输入是基本有序的，你却用第一个元素作为枢纽元)。

其实我们可以丢掉 Quick Sort 的分割算法，通过建立二叉排序树来得到一个理论上能与 Quick Sort 抗衡的排序算法。

    * 通过插入建立一棵平衡二叉树，时间界 O(nlog n)；
    * 先序遍历此树，得到排好序的序列，时间界 O(n)；

这样，总的时间界也是 O(nlog n)。这个算法在实践中当然不如 Quick Sort，因为 Quick Sort 的分割算法效率很高，而且最后不用去遍历一棵二叉树，但是它对于理解 Quick Sort 是有帮助的。

[ 本帖最后由 win_hate 于 2007-11-4 18:27 编辑 ]
作者: baohuaihuai    时间: 2007-11-04 19:36
看了版主的讲解,我想到一道关于quick sort的题:
"通常快速排序为了效率,都是选取中间点作为枢纽元. 现有从1到15,15个元素.请问这15个元素如何排列,能让选取中点作为枢纽元的排序方案也只能有O(n^2)的效率?"
作者: 扫地老僧    时间: 2007-11-04 22:21
多谢！ 豁然开朗
作者: lenovo    时间: 2007-11-04 23:29
好久不见老大，学习。
作者: yovn    时间: 2007-11-04 23:45
呵呵，我更倾向于“Quick Sort的精华在于分割“。
作者: win_hate    时间: 2007-11-05 00:33
多谢各位新老朋友捧场
作者: win_hate    时间: 2007-11-05 00:45
原帖由 yovn 于 2007-11-4 23:45 发表
呵呵，我更倾向于“Quick Sort的精华在于分割“。


Hoare 的分割方法确实巧妙。不过从理论上看，这个分割方法是相对次要的。只要分割是 O(n)  的，就能保证整个算法的平均时间为 O(nlog n)。设计一个 O(n) 的分割算法，不需要太多智慧，比如随便取一个枢纽元，然后与余下的数逐个比较，分别放到一个临时数组的两头，最后再复制回去－－－愚笨如此，仍是 O(n) 的。

Hoare 分割的贡献主要有两个：

1、可以就地(in-place)排序
2、效率高，可以打败其它 O(nlog n) 算法。

但 Quick Sort 背后的二叉树使得 Quick Sort 成为一个 O(nlog n) 的算法。如果抛弃就地排序的要求，Hoare 分割在我看来只是一个实现细节。
作者: ypxing    时间: 2007-11-05 08:35
个人认为精华在于:
找一个元素,然后进行分割,分治

原帖由 win_hate 于 2007-11-5 00:45 发表


Hoare 的分割方法确实巧妙。不过从理论上看，这个分割方法是相对次要的。只要分割是 O(n)  的，就能保证整个算法的平均时间为 O(nlog n)。设计一个 O(n) 的分割算法，不需要太多智慧，比如随便取一个枢纽元 ...
作者: halve    时间: 2007-11-05 10:08
原帖由 win_hate 于 2007-11-5 00:45 发表


Hoare 的分割方法确实巧妙。不过从理论上看，这个分割方法是相对次要的。只要分割是 O(n)  的，就能保证整个算法的平均时间为 O(nlog n)。设计一个 O(n) 的分割算法，不需要太多智慧，比如随便取一个枢纽元 ...

个人意见，精华在于分割
几种高效的排序算法如归并排序，快速排序都是这一思想的体现
只不过快排恰好在结构上与二叉树一致
昨天看<<啊!灵机一动>>，里头有个求最短路径的问题
用的是动态规划的方法，但最后结构上来说恰好和帕斯卡(杨辉)三角形一致
我们不能因此就说，精华在于这个帕斯卡三角形吧。。。

btw: 这个也是看问题角度不同的原因
可能 win_hate 看重的是二叉树这一结构在计算机中的广泛应用，而持有异议的人更注重分而治之的思路

[ 本帖最后由 halve 于 2007-11-5 10:43 编辑 ]
作者: win_hate    时间: 2007-11-05 12:32
Hoare 分割在整个算法中的地位是锦上添花还是画龙点睛？在这个问题上我们可以求同存异。

其实我想强调的是，学了一个算法，一个定理之后，应该花点时间想一想这个算法或定理是怎么得来的---即使这个问题可能没有答案，但仍是有益的。满足于能把算法实现或能把定理记住，都是不够的。


但我不能同意这位朋友的观点：

>>昨天看<<啊!灵机一动>>，里头有个求最短路径的问题
>>用的是动态规划的方法，但最后结构上来说恰好和帕斯卡(杨辉)三角形一致
>>我们不能因此就说，精华在于这个帕斯卡三角形吧。。。

用二叉树来排序，是个很自然，很聪明的想法；但用帕斯卡三角形来爬楼梯－－－则是一个很疯狂，很愚笨的想法。

[ 本帖最后由 win_hate 于 2007-11-5 12:36 编辑 ]
作者: ypxing    时间: 2007-11-05 12:36
其实堆排序等选择排序,也是利用了二叉树的
关键是怎样利用
qsort的关键就是分治与分割

原帖由 win_hate 于 2007-11-5 12:32 发表
Hoare 分割在整个算法中的地位是锦上添花还是画龙点睛？在这个问题上我们可以求同存异。

其实我想强调的是，学了一个算法，一个定理之后，应该花点时间想一想这个算法或定理是怎么得来的。满足于能把算法实现 ...
作者: win_hate    时间: 2007-11-05 12:41
堆排序如何使用了二叉树？
作者: ypxing    时间: 2007-11-05 12:43
堆排序没有利用二叉树吗?

原帖由 win_hate 于 2007-11-5 12:41 发表
堆排序如何使用了二叉树？
作者: win_hate    时间: 2007-11-05 12:44
我说的是二叉排序树，堆排序里的那个就叫堆
作者: ypxing    时间: 2007-11-05 12:48
其实也可以这样理解:
有了分治和分割
一个二叉排序树的形成就是很自然的了

可能又跑到先有鸡还是先有蛋的问题上了

原帖由 win_hate 于 2007-11-5 12:44 发表
我说的是二叉排序树，堆排序里的那个就叫堆
作者: win_hate    时间: 2007-11-05 12:53
分治是个很大很抽象很广泛的指导思想，在涉及具体问题的时候，有时会不知道如何使用它

而建二叉排序树的想法则具体得多。

随机建一个二叉排序树的最坏时间，最好时间，平均时间刚好与 Quick Sort  的时间相应。

[ 本帖最后由 win_hate 于 2007-11-5 12:54 编辑 ]
作者: yovn    时间: 2007-11-05 13:18
标题: 回复 #13 ypxing 的帖子
堆排序貌似用的完全二叉树。
作者: halve    时间: 2007-11-05 13:20
原帖由 halve 于 2007-11-5 10:08 发表
昨天看<<啊!灵机一动>>，里头有个求最短路径的问题
用的是动态规划的方法，但最后结构上来说恰好和帕斯卡(杨辉)三角形一致
我们不能因此就说，精华在于这个帕斯卡三角形吧。。。

sorry，这里有个记忆错误 ; (
应该是求2点间的所有路径组合问题，而不是最短路径
作者: cugb_cat    时间: 2008-03-27 16:03
这个问题，我也是觉得快速排序的基本出发点是分而治之，至于分割方法只是其中的细节。
作者: Sorehead    时间: 2008-03-27 18:15
我也同意快速排序的关键在于分割，其它的只是具体的实现方法而已。
作者: irhwe    时间: 2008-04-23 09:07
"通常快速排序为了效率,都是选取中间点作为枢纽元. 现有从1到15,15个元素.请问这15个元素如何排列,能让选取中点作为枢纽元的排序方案也只能有O(n^2)的效率?"
这个应该怎么做呢？
作者: xds2000    时间: 2008-07-30 17:10
#include <iostream>
using namespace std;

//quickSort algorithm
template < class T >
int partition(T a[], int p, int r){
T x = a[r];
int i = p-1;
  for(int j=p;j<r;j++){
    if(a[j] <= x){
     i++;
     swap(a,a[j]);
    }
  }
  swap(a[i+1], a[r]);
  return i+1;
}


template< class T >
void quickSort(T a[], int p, int r){
if(p < r){
  int q = partition(a, p , r);
  quickSort(a, p , q-1);
  quickSort(a, q+1 , r);
}
}

int main()
{
    int arr[]={23,31,4,9,12,7,59};
    int const n=sizeof(arr)/sizeof(arr[0]);
    for(int i=0;i<n;++i) cout<<"arr["<<i<<"]: "<< arr<<endl;
quickSort(arr,0,n);
cout<<"after sort: "<<endl;
for(int i=0;i<n;++i) cout<<"arr["<<i<<"]: "<< arr<<endl;

}
作者: reiase    时间: 2008-07-30 17:34
学习了



欢迎光临 Chinaunix (http://bbs.chinaunix.net/) Powered by Discuz! X3.2