快速排序(Quick Sort)是一種高效的排序算法,其基本思想是通過選取一個基準元素,將數組分為兩部分,使得一部分的元素都小于基準元素,另一部分的元素都大于基準元素,然后對這兩部分遞歸地進行快速排序,最終得到有序數組。
快速排序的實現步驟如下:
選取基準元素:從數組中選取一個元素作為基準元素,通常選取第一個元素、最后一個元素或者隨機選取。
劃分:遍歷數組,將小于基準元素的值放在基準元素的左邊,大于基準元素的值放在基準元素的右邊。完成一次劃分后,基準元素會處于正確的位置。
遞歸排序子數組:對基準元素左邊和右邊的子數組分別進行遞歸排序,直到子數組的長度為1或0。
以下是Java中快速排序的實現代碼:
public class QuickSort {
public static void main(String[] args) {
int[] arr = {3, 8, 2, 5, 1, 4, 7, 6};
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);
}
}
private static int partition(int[] arr, int low, int high) {
int pivot = arr[low];
int i = low;
int j = high;
while (i < j) {
while (i < j && arr[j] >= pivot) {
j--;
}
if (i < j) {
arr[i++] = arr[j];
}
while (i < j && arr[i] <= pivot) {
i++;
}
if (i < j) {
arr[j--] = arr[i];
}
}
arr[i] = pivot;
return i;
}
}
在這個例子中,我們首先定義了一個quickSort
方法,它接收一個整數數組、起始索引和結束索引作為參數。然后我們在partition
方法中實現了劃分操作,該方法返回基準元素的正確位置。最后,我們在main
方法中調用quickSort
方法對數組進行排序,并打印排序后的結果。