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;
}
}