quicksort:分治思想。

　　分解：数组A[p, r）被划分成两个子数组A[pq） 和 A[q+1, r），使得A[pq）中的每个元素小于等于A[q], A[q]也小于A[q+1r）中的每个元素。q是划分过程要返回的结果。

　　解决：递归调用quicksort,对子数组A[pq） 和 A[q+1, r）进行排序。

　　合并：因为子数组都是原址排序的，所以不需要合并操作：A[pr）已经有序。

　　代码数组下标从0开始，并且所有函数使用左闭右开区间。与算法导论第三版书上的伪代码不同的部分在注释标出。

　　#include <IOSTREAM>

　　#include <CSTDIO>

　　#include

　　#include <CTIME>

　　#include <CSTDLIB>

　　inline void swap（int &a, int &b）

　　{ int t = a; a = b; b = t; }

　　int partition（int *a, int p, int r） { //对 a[p, r） 原址重排

　　int x = a[r-1]; //a[r] ==> a[r-1]

　　int i = p - 1;

　　for （int j = p; j < r - 1; ++j）

　　if （a[j] <= x） {

　　++i;

　　swap（a[i], a[j]）；

　　}

　　swap（a[i+1], a[r-1]）；

　　return i + 1;

　　}

　　void quicksort（int *a, int p, int r） { //调用quicksort（a, 0, n），不是（a, 0, n-1），区间a[0, n）

　　if （p < r - 1） { //（p < r） ==> （p < r - 1）

　　int q = partition（a, p, r）；

　　quicksort（a, p, q）； //（a, p, q-1） ==> （a, p, q）

　　quicksort（a, q+1, r）；

　　}

　　}

　　int main（）

　　{

　　srand（time（NULL））；

　　int n;

　　while （scanf（"%d", &n）） {

　　int a[n];

　　for （int i = 0; i < n; ++i）

　　a[i] = rand（） % n;

　　for （int i = 0; i < n; ++i）

　　printf（"%d ", a[i]）；

　　printf（"\n"）；

　　quicksort（a, 0, n）；

　　for （int i = 0; i < n; ++i）

　　printf（"%d ", a[i]）；

　　printf（"\n"）；

　　}

　　} www.yz-jx.com

　　随机测试几万组数据与stl 的sort产生结果一致。

 

C++快速排序实现(quicksort),布布扣,bubuko.com

C++快速排序实现(quicksort)