Java快速排序的代码优化

在Java中，实现快速排序算法的一个常见方法是递归。为了优化这段代码，我们可以使用以下策略：

选择更好的基准值（pivot）：使用三数取中法或者随机选择基准值，这样可以减少不平衡分区的可能性，从而提高算法的性能。
尾递归优化：在递归调用时，先处理较小的分区，这样可以减少递归栈的深度，从而减少内存消耗。
当分区大小小于某个阈值时，使用简单的排序算法（如插入排序）处理分区，这样可以提高小规模数据集的处理速度。

下面是一个优化后的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方法中，我们使用了三数取中法来选择基准值。在递归调用时，我们先处理较小的分区，以减少递归栈的深度。

最新问答

相关标签