题目描述
给定你一个长度为n的整数数列。
请你使用快速排序对这个数列按照从小到大进行排序。
并将排好序的数列按顺序输出。
样例
5
3 1 2 4 5
时间复杂度
O(nlog2n)
Java 代码
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main{
public static void main(String[] args) throws IOException{
InputStreamReader in = new InputStreamReader(System.in);
BufferedReader br = new BufferedReader(in);
int num = Integer.parseInt(br.readLine());
int[] arr = new int[num];
String[] res = br.readLine().split(" ");
for (int i = 0; i < num; i++) {
arr[i] = Integer.parseInt(res[i]);
}
quickSort(arr, 0, num - 1);
for (int i = 0; i < num; i++) {
System.out.print(arr[i] + " ");
}
br.close();
}
//闫总快排模板 v.v
public static void quickSort(int[] q, int l, int r) {
if (l >= r) return;
int x = q[l+r>>1];
//Define positions of two pointers
int i = l - 1;
int j = r + 1;
while (i < j) {
do i++; while (q[i] < x);
do j--; while (q[j] > x);
//do Swap
if (i < j) {
int temp = q[i];
q[i] = q[j];
q[j] = temp;
}
}
quickSort(q, l, j);
quickSort(q, j + 1, r);
}
}
总觉得Java的写法太笨重了.. 有什么好的解决办法吗
quickSort(q, l, j);
quickSort(q, j + 1, r);
为什么j+1捏,而不是(q,l,i)-(q,i+1,r)
y总讲了,这里的写法涉及一个边界问题,防止死循环
写的几乎一样,英雄所见略同啊
int x = q[l+r>>1];
请问这里的>> 是什么意思?谢谢!
就是 (l+r) / 2,>> 就代表除以2,而且>>的优先级比”+”小,所以会先算 l+r
我代码和你一模一样,但是输入为” “的时候过不了
if(br.readLine().trim().isEmpty()) return ;
quickSort(q, l, j);
quickSort(q, j + 1, r);
这里 j 为什么不可以替换为 i
应该是while结束之后i>j了
可以换成
quickSort(q, l, i - 1);
quickSort(q, i, r);
https://www.acwing.com/activity/content/code/content/487415/
可以换的哈