complex的博客

这个算法是1960年由C.A.R.Hoare发明的。快速排序是尽量避免额外计算的一个极好例子，其工作方式就是在书组中划分出小的和大的元素：

    从书组中取出一个元素（基准值）；

    把其他元素分为两组：

        小的是那些小于基准值的元素；

        大的是那些大于基准值的元素。

    递归地对这两个组作排序。

一个简单的C语言实现代码：

    /*quicksort: sort v[0]..v[n-1] into increasing order*/

   void quicksort(int v[], int n)
   {
     int i;
     int last;
     if(n <= 1)    //nothing to do
     {
          return;
     }
     swap(v, 0, rand()%n)     //move pivot elem to v[0]
     last = 0;
     for(i=1; i
     {
          if(v[i] < v[0])
          {
                swap(v, ++last, i);
          }
     }
     swap(v, 0, last);      //restore pivot
     quicksort(v, last);    //recursively srot
     quicksort(v+last+1, n-last-1);    //each part
   }

其中调用的函数swap()如下：
    /*swap: interchange v[i] and v[j]*/
    void swap(int v[], int i, int j)
    {
       int temp;
       temp = v[i];
       v[i] = v[j];
       v[j] = temp;
    }