题目描述
给定你一个长度为n的整数数列。
请你使用快速排序对这个数列按照从小到大进行排序。
并将排好序的数列按顺序输出。
输入格式
输入共两行,第一行包含整数 n。
第二行包含 n 个整数(所有整数均在1~109109范围内),表示整个数列。
输出格式
输出共一行,包含 n 个整数,表示排好序的数列。
数据范围
1≤n≤1000001≤n≤100000
样例
输入样例:
5
3 1 2 4 5
输出样例:
1 2 3 4 5
分析
作为Acwing讲课的第一题,本题快速排序主要是基于分治及双指针的思想。对给定的一个序列,我们有多种排序方法,其中的快排,也就是接下来我们要讲的快速排序算法,可谓是较好的排序算法。
排序排序,我们肯定得需要一个参照物,比参照物小的数,我们可以归为一类,比参照物大的数,我们同样可以归为一类。对于这两类,我们又可以向刚才一样有进行下去,此时我们需要log2n个操作。
本题中,还有许多细节,需要我们处理。
细节
1 如何进行分治操作
2 如何处理两个指针的边界问题
3 对本题中,死循环问题是如何导致的
接下来我们将一一处理。
代码实现
#include <iostream>
using namespace std;
const int N=100010;
int q[N];
void quicksort(int q[],int l,int r)
{
if (l>=r) return ;
int x=q[(l+r)>>1];
int i=l-1,j=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]);
}
quicksort(q,l,j);
quicksort(q,j+1,r);
}
int main ()
{
int n;
cin>>n;
for (int i=0;i<n;i++)
{
cin>>q[i];
}
quicksort(q,0,n-1);
for(int i=0;i<n;i++)
{
cout<<q[i]<<" ";
}
return 0;
}
讲解
1 对于分治操作而言 有“分” 和“治”。 在分的过程中,我们将一段序列分为两段。接着通过特定操作,再进行治。
2 数组下标是从0开始的,但是在本题中 我们是对 i 先前进一格或 j 先后退一格 在判断他们是否小于或大于某个数。
因此,初始化 i=-1,j=n. 我们要清楚的认识到 当他们在靠近的过程中,最后一定是j在i的左边或j与i在同一个位置。
对于j在i的左边这一情况,当i移动到值为x的位置的时候,此时j恰好也在这个位置上,接着j向左移动一个位置即成立。
同样 j不在这个位置,一直向左移到跟i位置相同时,即在相同位置。
我们用j来当分界点时 第一段序列的右端点是j 第二端序列的左端点是j+1。
用i来当分界点时,第一段序列的右端点则是i-1 第二端序列的左端点是i
3 用i来当端点 我们需要额外注意,原因是在写x时,我们写 x=q[l]时,就会陷入死循环[0,1]这个区间
同样的对于j 我们不能写x=q[r]