题目描述
给定你一个长度为 n
的整数数列。
请你使用快速排序对这个数列按照从小到大进行排序。
并将排好序的数列按顺序输出。
输入格式
输入共两行,第一行包含整数 n
。
第二行包含 n
个整数(所有整数均在 1∼109
范围内),表示整个数列。
输出格式
输出共一行,包含 n
个整数,表示排好序的数列。
数据范围
1≤n≤100000
样例
输入样例:
5
3 1 2 4 5
输出样例:
1 2 3 4 5
相关知识点
bufferedreader输入、
使用Scanner会超时
InputStreamReader in = new InputStreamReader(System.in);
BufferedReader br = new BufferedReader(in);
int n = Integer.parseInt(br.readLine());//获取一行数据
String[] res = br.readLine().split(" ");//以空格为分隔符并存入到数组
快排算法注意事项
为使递归调用sort函数时更方便,所以采用使用中介i j
i小于j时才能交换
if(i<j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
快速排序模板
void sort(int[] a,int l,int r) {
//确保传入的数组元素至少为两个
if(l >= r) {
return ;
}
int k = a[l+r>>1];//右移一位,即除以2
//方便后续的do while循环
int i = l-1;
int j = r+1;
while(i<j) {
do {
i++;
}while(a[i] < k);
do {
j--;
}while(a[j] > k);
if(i<j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
sort(a,l,j);
sort(a,j+1,r);
}
答案
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
static int N = 100001;
public static void main(String[] args) throws IOException{
// TODO Auto-generated method stub
InputStreamReader in = new InputStreamReader(System.in);
BufferedReader br = new BufferedReader(in);
int n = Integer.parseInt(br.readLine());
int[] a = new int[N];
String[] res = br.readLine().split(" ");
for(int i=0;i<n;i++) {
a[i] = Integer.parseInt(res[i]);
}
int l = 0;
int r = n-1;
sort(a,l,r);
for(int i=0;i<n;i++) {
System.out.print(a[i]+" ");
}
}
static void sort(int[] a,int l,int r) {
if(l >= r) {
return ;
}
int k = a[l+r>>1];
int i = l-1;
int j = r+1;
while(i<j) {
do {
i++;
}while(a[i] < k);
do {
j--;
}while(a[j] > k);
if(i<j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
sort(a,l,j);
sort(a,j+1,r);
}
}