在Java中,實現快速排序算法的一個常見方法是遞歸。為了優化這段代碼,我們可以使用以下策略:
下面是一個優化后的Java快速排序實現:
public class QuickSort {
private static final int INSERTION_SORT_THRESHOLD = 47;
public static void quickSort(int[] arr) {
if (arr == null || arr.length <= 1) {
return;
}
quickSort(arr, 0, arr.length - 1);
}
private static void quickSort(int[] arr, int low, int high) {
while (low< high) {
if (high - low + 1 <= INSERTION_SORT_THRESHOLD) {
insertionSort(arr, low, high);
break;
}
int pivotIndex = partition(arr, low, high);
if (pivotIndex - low< high - pivotIndex) {
quickSort(arr, low, pivotIndex - 1);
low = pivotIndex + 1;
} else {
quickSort(arr, pivotIndex + 1, high);
high = pivotIndex - 1;
}
}
}
private static int partition(int[] arr, int low, int high) {
int mid = low + (high - low) / 2;
int pivot = medianOfThree(arr, low, mid, high);
swap(arr, pivot, high);
int i = low - 1;
for (int j = low; j< high; j++) {
if (arr[j] <= arr[high]) {
i++;
swap(arr, i, j);
}
}
swap(arr, i + 1, high);
return i + 1;
}
private static int medianOfThree(int[] arr, int low, int mid, int high) {
if (arr[low] > arr[mid]) {
swap(arr, low, mid);
}
if (arr[low] > arr[high]) {
swap(arr, low, high);
}
if (arr[mid] > arr[high]) {
swap(arr, mid, high);
}
return mid;
}
private static void insertionSort(int[] arr, int low, int high) {
for (int i = low + 1; i <= high; i++) {
int key = arr[i];
int j = i - 1;
while (j >= low && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
這個實現首先定義了一個閾值INSERTION_SORT_THRESHOLD
,當分區大小小于這個閾值時,使用插入排序處理分區。在partition
方法中,我們使用了三數取中法來選擇基準值。在遞歸調用時,我們先處理較小的分區,以減少遞歸棧的深度。