快排注意事项

使用以第一个元素为枢轴的快速排序：

import java.io.*; public class Main { static int[] arr = new int[200000]; static StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in))); static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); public static void quickSort(int left, int right) { int i = lfet, j = right, k = arr[left]; if(i>=j) { return; } while(i<j) { while(i<j && arr[j]>=k) { j--; } if(i<j) { arr[i] = arr[j]; i++; } while(i<j && arr[i]<=k) { i++; } if(i<j) { arr[j] = arr[i]; j--; } } arr[i] = k; quickSort(left, i-1); quickSort(i+1, right); } public static void main(String[] args) throws IOException{ st.nextToken(); int n = (int) st.nval; for(int i=0;i<n;i++) { st.nextToken(); arr[i] = (int) st.nval; } quickSort(0, n-1); for(int i=0;i<n;i++) { bw.write(arr[i]+" "); } bw.write("\n"); bw.close(); } }

这种方法当数列正好为倒序时，时间复杂度退化为O(n^2)，并不完美。 所以可以采用取中值作为枢轴的方法：

import java.util.*; import java.io.*; public class Main { static int[] arr = new int[200000]; static Scanner sc = new Scanner(System.in); static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); public static void quickSort(int left, int right) { int i = left, j = right, mid = (left+right)/2; int k = arr[mid]; while(i<=j) { while(arr[i]<k) { i++; } while(arr[j]>k) { j--; } if(i<=j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; i++; j--; } } if(j>left) { quickSort(left, j); } if(i<right) { quickSort(i, right); } } public static void main(String[] args) throws IOException{ int n = sc.nextInt(); for(int i=0;i<n;i++) { arr[i] =sc.nextInt(); } quickSort(0, n-1); for(int i=0;i<n;i++) { bw.write(arr[i]+" "); } bw.close(); } }

注意：使用取中值为枢轴排序一轮后: left<=j<=i<=right 另外还可以采用取随机数的方法。