旅游网站建设平台分析,网站建设公司 提成,wordpress 图片编辑,新网站推广方法今天的每日一题来自洛谷#xff0c;题目要求对给定的 N N N 个正整数进行从小到大的排序#xff0c;并输出结果。我们将使用经典的**快速排序算法#xff08;QuickSort#xff09;**来解决这一问题。下面我将从问题分析、代码实现、及快速排序的核心思想进行详细说明。
题…今天的每日一题来自洛谷题目要求对给定的 N N N 个正整数进行从小到大的排序并输出结果。我们将使用经典的**快速排序算法QuickSort**来解决这一问题。下面我将从问题分析、代码实现、及快速排序的核心思想进行详细说明。
题目分析
我们需要将输入的 N N N 个整数进行排序。根据题目给定的提示 N N N 的范围可以高达 1 0 5 10^5 105因此我们需要选用高效的排序算法。快速排序具有平均时间复杂度为 O ( N log N ) O(N \log N) O(NlogN)。 如果你不知道什么是快速排序以及不了解原理的可以看我另外几篇博客 【数据结构】分治算法经典: 快速排序详解【数据结构】时间复杂度和空间复杂度是什么 代码实现
//
// Created by XuanRan on 2024/10/18.
//#include iostreamusing 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 N N并通过 cin 将 N N N 个元素存入数组 arr 中。为了确保数组足够大这里将数组大小设定为 1 0 5 10^5 105 以上。
快速排序的实现
quickSort(int l, int r) 函数是快速排序的核心部分
我们选择数组中间的元素 mid 作为基准值。通过两个指针 x 和 y分别从左侧和右侧开始扫描数组将比基准值小的元素放在基准值左边比基准值大的元素放在基准值右边。当 x 和 y 指针相遇后递归地对左右两部分数组分别进行排序直到整个数组有序。
输出结果
排序完成后程序遍历数组并将排序好的元素输出。
快速排序的优缺点
优点
快速排序的平均时间复杂度是 O ( N log N ) O(N \log N) O(NlogN)相对于 O ( N 2 ) O(N^2) O(N2) 的冒泡排序、选择排序等效率更高。 空间开销小使用的是原地排序不需要额外的存储空间。
缺点
在最坏情况下如数组已经有序快速排序的时间复杂度会退化到 O ( N 2 ) O(N^2) O(N2)。 为了避免最坏情况可以采取随机选择基准值的策略即随机化快速排序Randomized QuickSort。
