一、算法导论上的版本

在我写的第二篇文章中，我们已经知道：

“再到后来，N.Lomuto又提出了一种新的版本，此版本....，即优化了PARTITION程序,它现在写在了 算法导论 一书上”：

快速排序算法的关键是PARTITION过程，它对A[p..r]进行就地重排：

PARTITION(A, p, r)

1  x ← A[r]         //以最后一个元素，A[r]为主元

2  i ← p - 1

3  for j ← p to r - 1    //注，j从p指向的是r-1，不是r。

4       do if A[j] ≤ x

5             then i ← i + 1

6                  exchange A[i] <-> A[j]

7  exchange A[i + 1] <-> A[r]    //最后，交换主元

8  return i + 1

然后，对整个数组进行递归排序：

QUICKSORT(A, p, r)

1 if p < r

2    then q ← PARTITION(A, p, r)   //关键

3         QUICKSORT(A, p, q - 1)

4         QUICKSORT(A, q + 1, r)

    根据上述伪代码，我们不难写出以下的c/c++程序：

首先是，PARTITION过程：

int partition(int data[],int lo,int hi) 

{

 int key=data[hi];  //以最后一个元素，data[hi]为主元

 int i=lo-1;

 for(int j=lo;j<hi;j++)   ///注，j从p指向的是r-1，不是r。

 {

  if(data[j]<=key)

  {

   i=i+1;

   swap(&data[i],&data[j]);

  }

 }

 swap(&data[i+1],&data[hi]);   //不能改为swap(&data[i+1],&key)

 return i+1;

}

补充说明：举个例子，如下为第一趟排序（更多详尽的分析请参考第二篇文章）：

第一趟(4步)：

   a：3   8   7   1   2   5   6   4   //以最后一个元素，data[hi]为主元

   b：3   1   7   8   2   5   6   4

   c：3   1   2   8   7   5   6   4

   d：3   1   2   4   7   5   6   8    //最后，swap(&data[i+1],&data[hi])

  而其中swap函数的编写，是足够简单的： 

void swap(int *a,int *b)

{

 int temp=*a;

 *a=*b;

 *b=temp;

}

    然后是，调用partition，对整个数组进行递归排序：

void QuickSort(int data[], int lo, int hi)

{

    if (lo<hi)

    {

        int k = partition(data, lo, hi);

        QuickSort(data, lo, k-1);

        QuickSort(data, k+1, hi);

    }

} 

int main()

{

const int MAX = 10;

int array[MAX] = {1, 2, 6, 2, 9, 0, 2, 4, 5, 3};

quicksort(array, 0, MAX-1);//这里为数组长度减1

for(int i = 0;i<MAX ;i++)

cout<<array[i]<<endl;

return 0;

}