C++算法实战之快速排序实战

一、简介：

Quicksort源于1961年 C.A.R.Hoare提出，正如名字那样，快速排序毫不夸张得在平均性能和巨大排序数量面前，都比其他基于比较的排序算法要好。

快速排序QuickSort 的最大功能之一是它是一种就地算法，它不使用任何额外的存储。Qsort 最聪明的技巧是在一个步骤中将一个大于枢轴的元素切换为一个较小的元素，它做的第一件事是将分组为“更少”和“更大”的堆时。

1.1 分而治之

快速排序的基本原理就是递归算法，每次递归都遵循分而治之的道理。伪代码如下

Recursion basis:
If n <=1, do nothing;
Recursive part(if n>1):
选出 "partitioning element" p
elements <= p, one element=p, elements >=p

当Recursion basis触发时视为recuse结束，且p左右的elements subarrays都递归完毕。

这里面有2个关键操作点：

1. 选择partitionin element方法
2. partition method

二、 partitiong method

描述如下：输入参数是数组a，和数组长度n，以及选定的partition element的索引ipart。

函数的原理如下代码所描述的。

1. 它会先把ipart位置所在的值partval取出来，ipart所在的位置放入数组最大索引的也就是a[n-1]值。这样之前的a就由 a[ipart]和连续存储位置的a数组所组成。

2. 接下来会进入一个循环体

这个循环体所做的事情就是交换partval左边的subarray和partval右边的subarry元素，达到partval左边的subarry元素都比它小，partval右边的subarray元素都比它大。具体操作细节如下：

游标 i 会从0开始不断地右移，直到遇到 i 所在的元素比partval大停止右移；

右边 j 会从 n-1开始不断地左移，直到遇到 j 所在的元素比partval小，停止左移；

此时 i 和 j所在的元素因为不满足规则“partval左边的subarry元素都比它小，partval右边的subarray元素都比它大

”，所以两个元素进行交换而达到满足这个规则。

3. 当i和j碰头时，结束循环体。此时的一次分而治之的数组变成

完整的代码如下：

代码语言：javascript复制

void partition_method(int* a, int n, int ipart)
{
    /* ipart: index of the partitioning element */
    int partval = a[ipart];
    int i = 0;
    int j = n-1;
    a[ipart] = a[j]; a[j--] = partval;
    bool done = false;
    do {
        while (a[i] < partval)
            i  ;
        while (i < j && partval < a[j])
            j--;
        if (j <= i)
            done = true;
        else {
            int temp = a[i]; a[i  ] = a[j]; a[j--] = temp;
        }
    } while (!done);
    a[n-1] = a[i]; a[i] = partval;
    /* subarray 1: a[0..(i-1)], partval, subarray 2: a[(i 1)..(n-1)] */
}



int main() {

    int a[10]={2,5,4,3,1,6,7,8,0,9};
    std::cout << "before partition_method" << std::endl;
    for (int i=0;i<10;i  )
        std::cout << std::to_string(a[i]) << " ";
    std::cout << std::endl;
    partition_method(a, 10, 2);
    std::cout << "after partition_method" << std::endl;
    for (int i=0;i<10;i  )
        std::cout << std::to_string(a[i]) << " ";
    std::cout << std::endl;
}

程序输出如下：

before partition_method
2 5 4 3 1 6 7 8 0 9
after partition_method
2 0 1 3 4 6 7 8 5 9

所以这里的main函数选取序号为2的元素a[2]=4作为 ipart的值。

将原来的a数组划分为两个子数组分别是 {2,0,1,3}和{6,7,8,5,9}

所以具体快速算法的复杂度跟待排序的数组是有关联的，合理的选择这个ipart可以优化快速排序复杂度。这个ipart的研究还可以继续深入探讨。

三完善快速排序函数

接下来继续完整快速排序函数

我们先对partition_method做下简单改造，让它能够返回分区后的新的ipart位置。然后my_quick_sort就可以根据ipart位置，对左右两边的subarray进行递归操作。