public class QuickSortor {
public static void main(String[] args) {
int[] a = { 8, 9, 3, 6 };
System.out.println("排序前的數組: " + Arrays.toString(a));
QuickSortor.quickSort(a, 0, a.length);
System.out.println("排序前的數組: " + Arrays.toString(a));
}
public static void quickSort(int[] arr, int startIndex, int endIndex) {
// 如果資料中的有效元素小于1 則直接傳回
if (endIndex - startIndex <= 1) {
return;
}
int metaData = arr[startIndex]; // 中繼資料(基準元素)
int leftIndex = startIndex; // 左邊開始索引
int rightIndex = endIndex - 1; // 右邊開始索引
while (leftIndex != rightIndex) {
// 從最右邊開始找比基準數小的元素
while (leftIndex < rightIndex && arr[rightIndex] >= metaData) {
rightIndex--;
}
// 從最左邊開始找比基準數大的元素
while (leftIndex < rightIndex && arr[leftIndex] <= metaData) {
leftIndex++;
}
if (leftIndex < rightIndex) {
QuickSortor.swap(arr, leftIndex, rightIndex);
}
}
// 基準元素歸位
QuickSortor.swap(arr, leftIndex, startIndex);
// 遞歸解決問題
QuickSortor.quickSort(arr, startIndex, leftIndex);
QuickSortor.quickSort(arr, leftIndex + 1, endIndex);
}
public static void swap(int[] arr, int rightIndex, int i) {
int temp = arr[rightIndex];
arr[rightIndex] = arr[i];
arr[i] = temp;
}
}