快速排序(Quick Sort)是一種常用的排序算法,它的基本思想是通過一趟排序將待排序的數據分割成獨立的兩部分,其中一部分的所有數據都比另一部分的所有數據小,然后再按此方法對這兩部分數據分別進行快速排序,整個排序過程可以遞歸進行,以此達到整個數據變成有序序列的目的。
以下是Java實現快速排序算法的示例代碼:
public class QuickSort {
public static void main(String[] args) {
int[] arr = {9, 2, 5, 7, 1, 8, 6, 3, 4};
quickSort(arr, 0, arr.length - 1);
for (int num : arr) {
System.out.print(num + " ");
}
}
public static void quickSort(int[] arr, int low, int high) {
if (low < high) {
// 將數組分區,并獲取分區點的索引
int pivotIndex = partition(arr, low, high);
// 對左側子數組進行快速排序
quickSort(arr, low, pivotIndex - 1);
// 對右側子數組進行快速排序
quickSort(arr, pivotIndex + 1, high);
}
}
public static int partition(int[] arr, int low, int high) {
// 將第一個元素作為分區點
int pivot = arr[low];
while (low < high) {
// 從右往左找到第一個小于分區點的元素
while (low < high && arr[high] >= pivot) {
high--;
}
// 將該元素放到左側
arr[low] = arr[high];
// 從左往右找到第一個大于分區點的元素
while (low < high && arr[low] <= pivot) {
low++;
}
// 將該元素放到右側
arr[high] = arr[low];
}
// 將分區點放到正確的位置上
arr[low] = pivot;
// 返回分區點的索引
return low;
}
}
上述代碼中,quickSort
方法實現了快速排序算法的遞歸調用,partition
方法用于將數組分區,并返回分區點的索引。在每一次遞歸調用中,選擇一個分區點將數組分成兩個子數組,然后對兩個子數組分別進行快速排序。最后,將分區點放到正確的位置上,完成一趟排序。通過遞歸調用快速排序算法,最終可以將整個數組排序。