洛谷9_3快速排序及其他

【模板】排序

题目描述

将读入的 $N$ 个数从小到大排序后输出。

输入格式

第一行为一个正整数 $N$。

第二行包含 $N$ 个空格隔开的正整数 $a_i$，为你需要进行排序的数。

输出格式

将给定的 $N$ 个数从小到大输出，数之间空格隔开，行末换行且无空格。

样例 #1

样例输入 #1

5
4 2 4 5 1

样例输出 #1

1 2 4 4 5

提示

对于 $20\%$ 的数据，有 $1 \leq N \leq 10^3$；

对于 $100\%$ 的数据，有 $1 \leq N \leq 10^5$，$1 \le a_i \le 10^9$。

题解

在9_2中我们已经讲解了选择排序、冒泡排序、插入排序，上文中我们最终通过充分利用了已经排序好的序列再结合二分查找来实现了插入排序的优化，最终时间复杂度为$O(n\log n)$，成功通过所有的测试点。在这其中，二分查找也就是分治的思想起到了至关重要的作用。

思路四：快速排序(Quick Sort)

分析思路：

• 快速排序是一种分治的排序算法，它的基本思想是通过一趟排序将待排序的数据分割成独立的两部分，其中一部分的所有数据都比另一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
• 因此本质上我们可以察觉到，实际上就是二分的思想，对比于插入排序，只不过一开始我们并没有营造一个有序的序列，而是先分成两部分，左边的比右边的小。
• 事实上从逻辑值的角度来看，本质上还是营造了0-1的有序序列，然后再递归地进行排序。
• 动画演示如下：

代码实现与详细注释

#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int n;
int a[N];
void quick_sort(int a[], int l, int r) 
{
    if (l >= r) return;
    int x = a[l + r >> 1];//取中间值作为基准值
    int i = l;//左指针一开始指向左边界
    int j = r;//右指针一开始指向右边界
    while (i <= j)//当左指针小于等于右指针时
    {
        while (a[i] < x) i++;//当左指针的值小于基准值时，左指针右移
        while (a[j] > x) j--;//当右指针的值大于基准值时，右指针左移
        //此时左指针的值大于等于基准值，右指针的值小于等于基准值
        if (i <= j) swap(a[i++], a[j--]);
        //交换两个值，然后继续移动左右指针
    }
    if (l < j) quick_sort(a, l, j);//如果左边界已经右移，递归左半部分
    if (i < r) quick_sort(a, i, r);//如果右指针已经左移，递归右半部分
}
int main() {
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> a[i];
    quick_sort(a, 0, n - 1);
    for (int i = 0; i < n; i++)
        cout << a[i] << ' ';
    return 0;
}

测试点结果：

算法分析

• 快速排序的时间复杂度为$O(n\log n)$，空间复杂度为$O(\log n)$，是一种非常高效的排序算法，但是在最坏情况下时间复杂度为$O(n^2)$，但是如果随机选择哨兵则很难出现最坏情况。
• 快速排序利用了01逻辑二分的思想，通过递归地分治，最终实现了排序的目的，在后面的我想还会探索一些其他的排序算法，如归并排序、堆排序等。
• 关于分治的思想，我们在这里也可以看到，实际上就是将一个大问题分解成小问题，然后递归地解决，最终合并结果，这是一种非常高效的解决问题的方法，也是一种非常重要的思想。