Quick Sort 的一个注记

前天参加一个讨论班，报告者在讲 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 是有帮助的。

---------------------------------------------------------

发表的：

#include
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     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< quickSort(arr,0,n);
cout<<"after sort: "< for(int i=0;i<
}