【每日一题】洛谷 - 快速排序模板

今天的每日一题来自洛谷，题目要求对给定的 $N$ 个正整数进行从小到大的排序，并输出结果。我们将使用经典的**快速排序算法（QuickSort）**来解决这一问题。下面我将从问题分析、代码实现、及快速排序的核心思想进行详细说明。

题目分析

我们需要将输入的 $N$ 个整数进行排序。根据题目给定的提示，$N$ 的范围可以高达 $10^5$，因此我们需要选用高效的排序算法。快速排序具有平均时间复杂度为 $O(N\log N)$。

如果你不知道什么是快速排序，以及不了解原理的可以看我另外几篇博客：

• 【数据结构】分治算法经典: 快速排序详解
• 【数据结构】时间复杂度和空间复杂度是什么？

代码实现

//
// Created by XuanRan on 2024/10/18.
//#include "iostream"using namespace std;int n;
long long arr[10 * 10 * 10 * 10 * 10 + 5];void quickSort(int l, int r)
{int x = l, y = r, mid = arr[(r + l) / 2];while (x < y){while (arr[x] < mid) x++;while (arr[y] > mid) y--;if (x <= y){swap(arr[x], arr[y]);x++;y--;}}if (y > l) quickSort(l, y);if (x < r) quickSort(x, r);
}int main(int argc, char* argv[])
{cin >> n;for (int i = 0; i < n; i++){cin >> arr[i];}quickSort(0, n - 1);for (int i = 0; i < n; i++){cout << arr[i] << " ";}
}

代码详解

输入与数组初始化

首先，程序读取输入的整数 $N$，并通过 cin 将 $N$ 个元素存入数组 arr 中。为了确保数组足够大，这里将数组大小设定为 $10^5$ 以上。

快速排序的实现

quickSort(int l, int r) 函数是快速排序的核心部分：

• 我们选择数组中间的元素 mid 作为基准值。
• 通过两个指针 x 和 y，分别从左侧和右侧开始扫描数组，将比基准值小的元素放在基准值左边，比基准值大的元素放在基准值右边。
• 当 x 和 y 指针相遇后，递归地对左右两部分数组分别进行排序，直到整个数组有序。

输出结果

排序完成后，程序遍历数组，并将排序好的元素输出。

快速排序的优缺点

优点：

快速排序的平均时间复杂度是 $O(N\log N)$，相对于 $O(N^2)$ 的冒泡排序、选择排序等，效率更高。
空间开销小，使用的是原地排序，不需要额外的存储空间。

缺点：

在最坏情况下（如数组已经有序），快速排序的时间复杂度会退化到 $O(N^2)$。
为了避免最坏情况，可以采取随机选择基准值的策略，即随机化快速排序（Randomized QuickSort）。