题目描述
blablabla
样例
blablabla
算法1
java 代码
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.StringTokenizer;
public class Main {
public static InputReader in = new InputReader(System.in);
public static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
public static void main(String[] args) throws Exception {
while(in.hasNext()) {
int n=in.nextInt();
int q[]=new int[n];
for (int i = 0; i < n; i ++ ) q[i]=in.nextInt();
quick_sort(q, 0, n - 1);
for (int i = 0; i < n; i ++ )out.printf("%d ", q[i]);
out.flush();//写在最后
}
out.close();
}
public static void quick_sort(int q[], int l, int r)
{
if (l >= r) return;
int i = l - 1, j = r + 1, x = q[l + r >> 1];
while (i < j)
{
do i ++ ; while (q[i] < x);
do j -- ; while (q[j] > x);
if (i < j) swap(i, j,q);
}
quick_sort(q, l, j);
quick_sort(q, j + 1, r);
}
private static void swap(int i, int j, int[] q) {
int tmp=q[i];
q[i]=q[j];
q[j]=tmp;
}
}
class InputReader{
private final static int BUF_SZ = 65536;
BufferedReader in;
StringTokenizer st;
public InputReader(InputStream in) {
super();
this.in = new BufferedReader(new InputStreamReader(in),BUF_SZ);
st = new StringTokenizer("");
}
public boolean hasNext() throws IOException {
while(!st.hasMoreTokens()){
String line = nextLine();
if(line == null){
return false;
}
st = new StringTokenizer(line);
}
return true;
}
public String next() throws IOException{
while (!st.hasMoreTokens()) {
try {
st = new StringTokenizer(in.readLine());
} catch (IOException e) {
throw new RuntimeException(e);
}
}
return st.nextToken();
}
public int nextInt() throws IOException {
return Integer.parseInt(next());
}
public double nextDouble() throws IOException {
return Double.parseDouble(next());
}
public double nextLong() throws IOException {
return Long.parseLong(next());
}
public String nextLine() throws IOException {
String line = "";
line = in.readLine();
return line;
}
}
算法1
java 代码
public class Main{
private static void quickSort(int[] arr, int low, int high) {
if (low < high) {
int middle = getMiddle(arr, low, high);
quickSort(arr, low, middle - 1);
quickSort(arr, middle + 1, high);
}
}
private static int getMiddle(int[] arr, int low, int high) {
int temp = arr[low];//pivot
while (low < high) {
while (low < high && arr[high] >= temp) {
high--;
}
arr[low] = arr[high];
while (low < high && arr[low] <= temp) {
low++;
}
arr[high] = arr[low];
}
arr[high] = temp;
return high;
}
public static void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
}