论坛徽章:: 0

电梯直达

1楼 [收藏(0)] [报告]

发表于 2007-11-04 18:21 |只看该作者 |正序浏览

这是我 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 编辑 ]

文库|博客

reiase

富足长乐

论坛徽章:: 0

23楼 [报告]

发表于 2008-07-30 17:34 |只看该作者

学习了

实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？

xds2000

白手起家

论坛徽章:: 0

22楼 [报告]

发表于 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;

}