AcWing 785. 快速排序

快速排序介绍

快速排序（\(Quick~Sort\)）由 \(C.A.R.Hoare\)（东尼·霍尔，\(Charles~Antony~Richard~Hoare\)）在 \(1960\) 年提出，之后又有许多人做了进一步优化。

如果你对快速排序感兴趣，可以去看看东尼·霍尔 \(1962\) 年在 \(Computer~Journal\) 发表的论文 “\(Quicksort\)” 以及《算法导论》的第七章。

快速排序思想

快速排序使用分治策略。

它的基本思想：选择一个 基准数，通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比基准数都要小，另一部分的所有数据都比基准数都要大。然后，再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

快速排序流程

  • 从数列中挑出一个基准值；
  • 将要排序的数据分割成独立的两部分，其中一部分的所有数据都比基准数都要小，另一部分的所有数据都比基准数都要大（相同的数可以到任意一边），这部我们称为“分块”；
  • 递归地把左右两边分别排好序。

如何分块？

为了实现一次分块，我们可以从数组的两端移动下标，必要时交换记录，直到数组两端的下标相遇为止。

为此，我们附设两个指针 \(i\) 和 \(j\)， 通过 \(j\) 从当前序列的有段向左扫描，越过不小于基准值的记录。当遇到小于基准值的记录时，扫描停止。

通过 \(i\) 从当前序列的左端向右扫描，越过小于基准值的记录。当遇到不小于基准值的记录时，扫描停止。

交换两个方向扫描停止的记录 \(a_j\) 与 \(a_i\)。

然后，继续扫描，直至 \(i\) 与 \(j\) 相遇为止。扫描和交换的过程结束。

这时 \(i\) 左边的记录的关键字值都小于基准值，右边的记录的关键字值都不小于基准值。

动图演示

算法稳定性与时间复杂度

快速排序稳定性

算法稳定性：假设在数列中存在 \(a_i = a_j\)，若在排序之前，\(a_i\) 在 \(a_j\) 前面；并且排序之后，\(a_i\) 仍然在 \(a_j\) 前面,则这个排序算法是稳定的。

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

快速排序时间复杂度

快速排序的时间复杂度在最坏情况下是 \(O(n^2)\)，平均的时间复杂度是 \(O(nlogn)\)。

这句话很好理解：假设被排序的数列中有 \(n\) 个数,遍历一次的时间复杂度是 \(O(n)\)，需要遍历多少次呢？至少 \(logn\) 次，最多 \(N\) 次。

  • 为什么最少是 \(logn\) 次？
    快速排序是采用的分治法进行遍历的，我们将它看作一棵二叉树，它需要遍历的次数就是二叉树的深度，而根据完全二叉树的定义，它的深度至少是 \(logn\)。因此，快速排序的遍历次数最少是 \(logn\) 次。
  • 为什么最多是 \(n\) 次？
    这个非常简单，还是将快速排序看作一棵二叉树，它的深度最大是 \(n\)。因此，快读排序的遍历次数最多是 \(n\) 次。

快速排序实现

#include 
#include 
#include 
#include 
#include 
using namespace std;

const int N = 100010;

int a[N]; //需要排序的数组

void quick_sort(int q[], int l, int r)
{
    int x = q[(l + r) / 2], i = l - 1, j = r + 1; //x为基准数（开“(l + r) / 2”会比“l”更快，我太弱了，不会证QAQ，但这提开“l”会TLE）
    if (l >= r)
    {
        return;
    }
    while (i < j)
    {
        while (q[ ++ i] < x); //移动指针i
        while (q[ -- j] > x); //移动指针j
        if (i < j) //判断相遇
        {
            swap(q[i], q[j]); //交换
        }
    }
    //分别将左右两边排序
    quick_sort(q, l, j);
    quick_sort(q, j + 1, r);
}

int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++ )
    {
        scanf("%d", &a[i]);
    }
    quick_sort(a, 1, n);
    for (int i = 1; i <= n; i ++ )
    {
        printf("%d ", a[i]);
    }
    return 0;
}

参考资料：《啊哈！算法》

C++算法ACWING基础课

相关

标签