数据结构笔记（十）排序算法之快速排序

快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。它采用了一种分治的策略，通常称其为分治法(Divide-and-ConquerMethod)。

分治法的基本思想：将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题，然后将这些子问题的解组合为原问题的解。

基本思想

从数列中挑出一个元素，称为“基准”（pivot）
开始分区（partition）操作：所有比基准值小的元素摆放在基准左边，所有比基准值大的元素摆在基准右边（相同的数可以到任何一边）。在这个分区结束之后，该基准就处于数列的中间位置。
递归地（recursively）把小于基准值元素的子数列和大于基准值元素的子数列排序。

递归到最底部时，数列的大小是零或一，也就是已经排序好了。这个算法一定会结束，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。

图文演示

现有一批书KDBSEIMCSGAQZJNVYPLTUFWHRO需要按照字母编号排序，如图所示。

①首先从中任意选取一本书N作为基准。

②然后把书堆分成两半，编号比基准值小的放左边，编号比基准值大的放右边。

③只看基准值左边的部分，从中任意选取一本书G作为新基准，按照②分成两半；只看基准值右边的部分，从中任意选取一本书T作为新基准，按照②分成两半。

④继续执行③直至结束。

现有一个数字序列29,5,47,15,36,26,27,2,46,4,19,50,48，对其进行快速排序。

首先选择序列第一个数29作为基准，然后将其分成左右两个序列，小于29的放左边，大于29的放右边。

[左序列]选择19作为基准，然后分成两个序列。

[左序列]选择4作为基准，然后分成两个序列。

[左序列]依次选择15、26作为基准，直至左序列有序。

[右序列]依次选择46、47、50作为基准，直至右序列有序。

整个序列有序。

算法实现

版本一

#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <ctime>
using namespace std;

const int maxn = 100;
const int Max = 100;
int a[maxn];

void display(int a[], int n) // 数组显示输出
{
    for (int i = 0; i < n; ++i)
    {
        cout << a[i] << " ";
        if ((i+1) % 5 == 0)
            cout << endl;
    }
}

int _partition(int a[], int low, int high) // 分区操作
{
    int ret = low;
    int pivot = a[ret]; // 选择第一个值作为基准
    for (int i = low + 1; i <= high; ++i)
    {
        if (a[i] < pivot) // 小于基准值的交换位置
        {
            a[ret] = a[i];
            a[i] = a[++ret];
        }
    }
    a[ret] = pivot;
    return ret; // 返回基准值位置
}

void quicksort(int a[], int low, int high) // 排序操作
{
    if (low >= high)
        return ;
    int pivot = _partition(a, low, high); // 基准值已排好
    quicksort(a, low, pivot-1);  // 左边子序列递归
    quicksort(a, pivot+1, high); // 右边子序列递归
}

int main()
{
    for (int i = 0; i < maxn; ++i)
        a[i] = rand() % Max;
    display(a, maxn);
    clock_t _start, _end;
    _start = clock();
    quicksort(a, 0, maxn-1);
    _end = clock();
    cout << (double)(_end - _start) / CLOCKS_PER_SEC << endl;
    display(a, maxn);
    return 0;
}

随机测试了了100个数，耗时0s
41 67 34 0 69
24 78 58 62 64
5 45 81 27 61
91 95 42 27 36
91 4 2 53 92
82 21 16 18 95
47 26 71 38 69
12 67 99 35 94
3 11 22 33 73
64 41 11 53 68
47 44 62 57 37
59 23 41 29 78
16 35 90 42 88
6 40 42 64 48
46 5 90 29 70
50 6 1 93 48
29 23 84 54 56
40 66 76 31 8
44 39 26 23 37
38 18 82 29 41
0
0 1 2 3 4
5 5 6 6 8
11 11 12 16 16
18 18 21 22 23
23 23 24 26 26
27 27 29 29 29
29 31 33 34 35
35 36 37 37 38
38 39 40 40 41
41 41 41 42 42
42 44 44 45 46
47 47 48 48 50
53 53 54 56 57
58 59 61 62 62
64 64 64 66 67
67 68 69 69 70
71 73 76 78 78
81 82 82 84 88
90 90 91 91 92
93 94 95 95 99

版本二

#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <ctime>
using namespace std;

const int maxn = 10000000;
const int Max = 30000;
int a[maxn];

void quick_Sort(int a[], int low, int high)
{
    if (low >= high)
        return ;
    int l = low, r = high;
    int x = a[l];
    while (l < r)
    {
        while (l < r && x < a[r]) // 从右到左找到第一个小于x的数
            --r;
        if (l < r) // 交换
            a[l++] = a[r];
        while (l < r && a[l] < x) // 从左到右找到第一个大于x的数
            ++l;
        if (l < r) // 交换
            a[r--] = a[l];
    }
    a[l] = x; 
    quick_Sort(a, low, l-1); // 左递归
    quick_Sort(a, l+1, high); // 右递归
}

int main()
{
    for (int i = 0; i < maxn; ++i)
        a[i] = rand() % Max;
    //display(a, maxn);
    clock_t _start, _end;
    _start = clock();
    quick_Sort(a, 0, maxn-1);
    _end = clock();
    cout << (double)(_end - _start) / CLOCKS_PER_SEC << endl;
    //display(a, maxn);
    return 0;
}

测试排序时间
30000内随机数
1000000   0.28s
10000000  2.861s
50000000  13.291s
100000000 20.023s

说明：版本一在测试数量达到五百万时就得等待较长时间，测一千万时间为29s。

测时间的调用函数可能会好一些。

void getTime(void f(int [], int, int), int a[], int l, int r)
{
    clock_t _start, _end;
    _start = clock();
    f(a, l, r);
    _end = clock();
    cout << (double)(_end - _start) / CLOCKS_PER_SEC << endl;

for (int i = 0; i < maxn; ++i)
    a[i] = rand() % Max;
copy(a, a+maxn, b);
getTime(quicksort, b, 0, maxn-1);
copy(a, a+maxn, b);
getTime(quick_Sort, b, 0, maxn-1);

算法分析

快速排序稳定性
快速排序是不稳定的算法，它不满足稳定算法的定义。

快速排序时间复杂度
快速排序的时间复杂度在最坏情况下是O(N²)，平均的时间复杂度是O(N*lgN)。
这句话很好理解：假设被排序的数列中有N个数。遍历一次的时间复杂度是O(N)，需要遍历多少次呢？至少lg(N+1)次，最多N次。
①为什么最少是lg(N+1)次？快速排序是采用的分治法进行遍历的，我们将它看作一棵二叉树，它需要遍历的次数就是二叉树的深度，而根据完全二叉树的定义，它的深度至少是O(N²)。因此，快速排序的遍历次数最少是lg(N+1)次。
②为什么最多是N次？这个应该非常简单，还是将快速排序看作一棵二叉树，它的深度最大是N。因此，快读排序的遍历次数最多是N次。

补充

快速排序是二叉查找树（二叉查找树）的一个空间最优化版本。不是循序地把数据项插入到一个明确的树中，而是由快速排序组织这些数据项到一个由递归调用所隐含的树中。这两个算法完全地产生相同的比较次数，但是顺序不同。对于排序算法的稳定性指标，原地分区版本的快速排序算法是不稳定的。其他变种是可以通过牺牲性能和空间来维护稳定性的。

快速排序的最直接竞争者是堆排序（Heapsort）。堆排序通常比快速排序稍微慢，但是最坏情况的运行时间总是 O(nlogn)。快速排序是经常比较快，除了introsort变化版本外，仍然有最坏情况性能的机会。如果事先知道堆排序将会是需要使用的，那么直接地使用堆排序比等待introsort再切换到它还要快。堆排序也拥有重要的特点，仅使用固定额外的空间（堆排序是原地排序），而即使是最佳的快速排序变化版本也需要 O(logn)的空间。然而，堆排序需要有效率的随机存取才能变成可行。

快速排序也与归并排序（Mergesort）竞争，这是另外一种递归排序算法，但有最坏情况 O(nlogn)运行时间的优势。不像快速排序或堆排序，归并排序是一个稳定排序，且可以轻易地被采用在链表（linked list）和存储在慢速访问媒体上像是磁盘存储或网络连接存储的非常巨大数列。尽管快速排序可以被重新改写使用在链串列上，但是它通常会因为无法随机存取而导致差的基准选择。归并排序的主要缺点，是在最佳情况下需要 O(n)额外的空间。

快速排序还有很多改进版本，如随机选择基准数，区间内数据较少时直接用另的方法排序以减小递归深度。

说明

本文基础知识部分与补充部分来源于维基百科，算法分析部分来自于skywang12345。

数据结构笔记（十）排序算法之快速排序

基本思想

图文演示

算法实现

算法分析

补充

说明

推荐