java
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class Main {
public static void quickSort(int[] arr, int left, int right) {
if(left >= right) return;
//1. 确定基准值
int pivot = arr[(left + right) / 2];
//2. 排序
int i = left - 1, j = right + 1;
while(i < j) {
do i++; while(arr[i] < pivot);
do j--; while(arr[j] > pivot);
if(i < j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
quickSort(arr, left, j);
quickSort(arr, j + 1, right);
}
public static void main(String[] args) throws Exception {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(reader.readLine());
int[] arr = new int[n];
String[] str = reader.readLine().split(" ");
for(int i = 0; i < n; i++) {
arr[i] = Integer.parseInt(str[i]);
}
quickSort(arr, 0, n - 1);
for(int i = 0; i < n; i++) {
System.out.print(arr[i] + " ");
}
}
}
注意点:
10
49 59 88 37 98 97 68 54 31 3
在递归排序时,使用的分界值是j,不能是i。在上例中,pivot=98,当我们的i指向4,j指向9时,就会进行交换,则原数组为
49 59 88 37 3 97 68 54 31 98
此时i < j,进入while循环,由于没有比98还要小的,i会直接指向9,而我们采用的是do while,也就是说,不管什么情况,j都先减减,则j会指向8,此时if和while语句判断都为false,进入递归,如果使用i作为分界值,接下来就会出现quickSort(arr, 0, 9),quickSort(arr, 10, 9)。程序就无法得出正确的答案。