AcWing 785. 快速排序

[toc]

琢磨太深，使人痛苦！！！
琢磨太深，使人痛苦！！！
琢磨太深，使人痛苦！！！

推荐阅读：

785. 快速排序 - AcWing【简单】

一、题目描述

给定你一个长度为 n 的整数数列。
请你使用快速排序对这个数列按照从小到大进行排序。
并将排好序的数列按顺序输出。

输入格式
输入共两行，第一行包含整数 n。

第二行包含 n 个整数（所有整数均在 1∼109 范围内），表示整个数列。

输出格式
输出共一行，包含 n 个整数，表示排好序的数列。

数据范围：

1≤n≤100000

输入样例：

5
3 1 2 4 5

输出样例：

1 2 3 4 5

二、AC代码

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 1e6 + 10;
int q[N];
void quick_sort(int q[], int l, int r);

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

void quick_sort(int q[], int l, int r)
{
    if (l >= r) return;
    
    // q[l]时间超限、q[r]内存超限、q[(l + r) / 2]通过
    int i = l - 1, j = r + 1, x = q[l + r >> 1];
    while (i < j)
    {
        do i++; while (q[i] < x);
        do j--; while (q[j] > x);
        if (i < j) swap(q[i], q[j]);
    }
    quick_sort(q, l, j);
    quick_sort(q, j + 1, r);
}

三、错误分析

基准位置的选择问题

视频里y总用的是 q[l]，过了——但是网站里的模板是 q[l + r >> 1]

  1. 尝试 q[l]：Time Limit Exceeded

  2. 尝试 q[r]：Memory Limit Exceeded

  3. 尝试 q[l + r >> 1]、q[l + (r - l) >> 1] 和 q[(l + r) / 2] 、q[l + (r - l) / 2]：Accepted

但其实 q[(l + r) / 2] 和 q[l + r >> 1] 都是不对的：

  1. 溢出问题
    q[(l + r) / 2] 和 q[l + r >> 1] 中尽管除了2，但是 l + r 是可能溢出的，会超出 int 的整数范围

  2. 运算符优先级、规范问题
    在 q[l + r >> 1] 中这个写法是不规范的，虽然 >> 优先级比较低，但是编译器会提示：

    [警告] suggest parentheses around '+' inside '>>' [-Wparentheses]

    这个警告的意思是编译器建议在 (r - l) / 2 这个表达式中的 + 周围加上括号，以明确运算的顺序。这是由于 C++ 中运算符的优先级，+ 的优先级高于右移运算符 >>，因此在不加括号的情况下，编译器会先执行加法，然后再进行右移操作。
    虽然在这种情况下不加括号也是合法的，但为了代码的清晰度和防止可能的误解，编译器给出了这个警告。
    所以，加上 ()比较好。

四、总结

1. 基准位置的写法

q[(l + (r - l)) >> 1] ：使用位运算右移 >>，在很多情况下性能相对较好，因为位运算通常比除法运算更快。
q[l + (r - l) / 2]：使用除法运算 /，更直观，可读性更好，而且在大多数现代编译器和处理器上，性能差异可能不太明显。

所以我还是喜欢：l + (r - l) / 2。

2. 基准位置选择中间位置的原因

选择数组的中间位置作为快速排序的基准元素是一种常见的做法，这是因为在很多情况下它能够提高快速排序的性能。这是基于以下考虑：

  1. 均匀分割： 选择中间位置的元素可以使数组在每一轮分割中相对均匀地被划分成两部分。这有助于确保在每次分割中，基准元素两侧的元素数量相对平衡。
  2. 减少最坏情况发生的概率： 在选择中间位置的元素作为基准的情况下，快速排序在平均情况下的性能较好。虽然快速排序的平均时间复杂度为 O(nlogn)，但在最坏情况下，它可能达到 O(n^2)。通过选择中间位置，有助于减少最坏情况发生的概率。
  3. 避免有序性对性能的影响： 如果选择第一个或最后一个元素作为基准，而数组已经有序，那么在每一轮分割中都可能导致不均匀的划分，性能下降。选择中间位置的元素能够在某种程度上避免这种情况。
    总的来说，选择中间位置的元素是一种在大多数情况下表现良好的策略，有助于提高快速排序的效率。然而，在某些特殊情况下，也有其他选择基准的方法，这取决于具体的实现和问题要求。

3. 快速排序算法的证明与边界分析 【了解】

1

琢磨太深，使人痛苦！！！
琢磨太深，使人痛苦！！！
琢磨太深，使人痛苦！！！

顺带一提用 i 做划分时的模板

void quick_sort(int q[], int l, int r) 
{
    if (l >= r) return;
    int i = l - 1, j = r + 1;
    int x = q[(l + r + 1) >> 1]; // 非得要用i这里要修改！

    while (i < j) 
    {
        do i++; while (q[i] < x);
        do j--; while (q[j] > x);
        if (i < j) swap(q[i], q[j]);
    }
    quick_sort(q, l, i - 1), quick_sort(q, i, r); // 非得要用i这里要修改！
}