题目描述
给定你一个长度为 n 的整数数列。
请你使用快速排序对这个数列按照从小到大进行排序。
并将排好序的数列按顺序输出。
输入格式
输入共两行,第一行包含整数 n。
第二行包含 n 个整数(所有整数均在 1∼109 范围内),表示整个数列。
输出格式
输出共一行,包含 n 个整数,表示排好序的数列。
数据范围
1≤n≤100000
样例
输入样例:
5
3 1 2 4 5
输出样例:
1 2 3 4 5
分析
首先确定一个数组中的元素x,然后在数组两端设置两个指针i和j,将两个指针往确定元素方向移动,依次判断每个元素与确定元素的大小,当指针i指向的元素>=x和指针j指向的元素<=x时,交换这两个元素,直到i>=j时停止。
第一次迭代后的结果是元素x左边的元素都小于等于x,x右边的元素都大于等于x,然后再对x的左右两边进行如上操作。
关键点
在于对边界的确定
Java代码
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
public static void main(String[] args) throws IOException {
//System.in ->字节流,通过通过 InputStreamReader 变成字符流 再通过 BufferedReader 变成字符缓冲流
//自己实现键盘录入数据:
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int num = Integer.parseInt(br.readLine()); //首先输入数组长度,将得到的字符串类型的数据转换为整数类型
int arr[] = new int[num];
//向数组中添加元素
//split 方法的结果是一个字符串数组
String[] ss = br.readLine().split(" "); //输入数组元素,通过split方法分割成字符串数组
//将字符串数组中的元素逐一添加到整数数组arr中
for (int i = 0; i < arr.length; i++){
arr[i] = Integer.parseInt(ss[i]); //将字符串中的元素转换为整数添加到整数数组arr中
}
quick_sort(arr, 0, num - 1);
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
br.close();
}
public static void quick_sort(int q[], int l, int r) {
if (l >= r) return;
//定义两个指针
//i先放在索引-1处,j放在索引num处
int i = l - 1;
int j = r + 1;
//确定一个数x,x可以是q[l],q[r],或者是q[l + r >> 1]
/*
java中有三种移位运算符
<<:左移运算符,num << 1,相当于num乘以2
>>:右移运算符,num >> 1,相当于num除以2
>>>:无符号右移,忽略符号位,空位都以0补齐
*/
int x = q[l];
while (i < j) {
do {
i++;
} while (q[i] < x);
//直到不满足 q[i] < x 时,停下
do {
j--;
} while (q[j] > x);
//直到不满足 q[i] > x 时,停下
//当 i 和 j 都停下时,交换两个数字
if (i < j) {
int temp = q[i];
q[i] = q[j];
q[j] = temp;
}
}
//这个时候数列已经被分成了左边是小于x,右边是大于x的
//再分别对前后两部分进行排序
//此时x不能取 q[r],q[l + r + 1 >> 1]
//x = q[l + r >> 1] 或者 x = q[l]:边界问题
quick_sort(q, l, j);
quick_sort(q, j + 1, r);
//此时x不能取 q[l],q[l + r >> 1]
//x = q[l + r + 1 >> 1] 或者 x = q[r]:边界问题
// quick_sort(q, l, i-1);
// quick_sort(q, i, r);
}
}