←麻烦点一下这个好嘛QWQ
题目描述
给定你一个长度为 $n$ 的整数数列。
请你使用快速排序对这个数列按照从小到大进行排序。
并将排好序的数列按顺序输出。
输入格式
输入共两行,第一行包含整数 $n$。
第二行包含 $n$
个整数(所有整数均在 $1$∼$10⁹$ 范围内),表示整个数列。
输出格式
输出共一行,包含 $n$ 个整数,表示排好序的数列。
数据范围
$1≤n≤100000$
输入样例
5
3 1 2 4 5
输出样例
1 2 3 4 5
题意
题意很简单,就是输入n个数字,再让我们排序,最后输出就行了
算法1
普通快排
先定义什么我就不说了
思路:
先确定一个分解点(x),可以是左边界,右边界,中间值,随机数。但是本题数据已加强,所以不能去左边界和右边界了。
然后就是调整区间。
调整区间有两种方法。
第一种(暴力调整,时间复杂度$O(n)$线性):开两个临时数组a、b,扫描整个区间,如果q[i] < x 则把q[i]放到a里面,否则放到b里面,最后把a、b里面的数放回q数组里面
第二种(类似双指针):定义两个临时指针i、j,两个指针分别往中间走,i先走,如果q[i] < x 则把q[i]放到左半边,然后接着移动,一直移动,直到q[i] >= x则停下来。同理j也是如此:j后走,如果q[j] >= x 则把q[j]放到右半边,然后接着移动,一直移动,直到q[i] < x则停下来,最后把i、j所指的数交换一下就可以了(可以用库函数swap)。
最后递归处理左右两端。
时间复杂度
$O(nlog₂n)$
参考文献
视频讲解1
视频讲解2
图片讲解:
B站(bilibili)讲解
代码模板
void quick_sort(int a[], int l, int r){
if (l >= r) return;
int x = a[(l + r) / 2], i = l - 1, j = r + 1;
while (i < j){
do i++; while (a[i] < x);
do j--; while (a[j] > x);
if (i < j) swap(a[i], a[j]);
}
quick_sort(a, l, j);
quick_sort(a, j + 1, r);
}
C++ 代码
#include <bits/stdc++.h>
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) / 2], i = l - 1, j = r + 1;
while (i < j){
do i++; while (a[i] < x);
do j--; while (a[j] > x);
if (i < j) swap(a[i], a[j]);
}
quick_sort(a, l, j);
quick_sort(a, j + 1, r);
}
int main(){
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
quick_sort(a, 1, n);
for (int i = 1; i <= n; i++) cout << a[i] << " ";
return 0;
}
算法2
c++ STL库函数
完全就是c++STL里面的库函数sort,sort语法:sort(数组名称 + 初始下标, 数组名称 + 排序结尾数字 + 初始下标, 一个比较函数),当然,比较函数可以不加上
sort常规写法
sort(a, a + n); 或 sort(a + 1, a + n + 1); 或 sort(a, a + n, cmp(x, y));
C++代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n;
int a[N];
int main(){
cin >> n;
for (int i = 0; i < n; i++) cin >> a[i];
sort(a, a + n);
for (int i = 0; i < n; i++) cout << a[i] << " ";
return 0;
}