public class QuickSort {
public static void quickSortHelp(int[] arr) {
quickSort(arr, 0, arr.length - 1);
}
public static int division(int[] list, int left, int right) {
// 以最左邊的數(left)為基準
int base = list[left];
while (left < right) {
// 從序列右端開始,向左周遊,直到找到小于base的數
while (left < right && list[right] >= base) {
right--;
}
// 找到了比base小的元素,将這個元素放到最左邊的位置
list[left] = list[right];
// 從序列左端開始,向右周遊,直到找到大于base的數
while (left < right && list[left] <= base) {
left++;
}
// 找到了比base大的元素,将這個元素放到最右邊的位置
list[right] = list[left];
}
// 最後将base放到left位置。此時,left位置的左側數值應該都比left小;
// 而left位置的右側數值應該都比left大。
list[left] = base;
return left;
}
private static void quickSort(int[] list, int left, int right) {
// 左下标一定小于右下标,否則就越界了
if (left < right) {
// 對數組進行分割,取出下次分割的基準标号
int base = division(list, left, right);
// 對“基準标号“左側的一組數值進行遞歸的切割,以至于将這些數值完整的排序
quickSort(list, left, base - 1);
// 對“基準标号“右側的一組數值進行遞歸的切割,以至于将這些數值完整的排序
quickSort(list, base + 1, right);
}
}
public static void main(String[] args) {
int[] array = {1, 5, 4, 7, 3, 15, 24, 36, 111, 11, 2};
quickSortHelp(array);
for (int s : array) {
System.out.println(s);
}
}
}