Java排序算法总结（七）：快速排序(Java快速排序算法详解（七）：高效排序技巧总结)

一、迅速排序简介

迅速排序（Quick Sort）是一种高效的排序算法，由英国计算机科学家东尼·霍尔（Tony Hoare）在1960年提出。它的基本思想是分治法，通过递归地将大问题分解为小问题来解决。迅速排序的平均时间纷乱度为O(n log n)，在最坏的情况下为O(n^2)，但实际应用中表现良好，是常用排序算法之一。

二、迅速排序的基本步骤

迅速排序首要包括以下步骤：

1. 从数组中选取一个元素作为基准（pivot）。
2. 将数组分为两个子数组，一个包含小于基准的元素，另一个包含大于基准的元素。
3. 递归地对这两个子数组进行迅速排序。
4. 合并排序好的子数组。

三、迅速排序的实现

以下是迅速排序的Java实现代码：

public class QuickSort {
    public static void quickSort(int[] arr, int left, int right) {
        if (left < right) {
            int pivotIndex = partition(arr, left, right);
            quickSort(arr, left, pivotIndex - 1);
            quickSort(arr, pivotIndex + 1, right);
        }
    }
    private static int partition(int[] arr, int left, int right) {
        int pivot = arr[right];
        int i = left - 1;
        for (int j = left; j < right; j++) {
            if (arr[j] < pivot) {
                i++;
                swap(arr, i, j);
            }
        }
        swap(arr, i + 1, right);
        return i + 1;
    }
    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    public static void main(String[] args) {
        int[] arr = {9, 5, 2, 7, 3, 6, 8};
        quickSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }
}

四、迅速排序的优化

虽然迅速排序在平均情况下表现良好，但在最坏情况下时间纷乱度为O(n^2)。以下是一些常用的优化技巧：

1. 选择合适的基准元素

最坏情况出现在每次选择的基准元素都是最小或最大的元素。为了避免这种情况，可以采用以下策略：

• 随机选择基准元素。
• 选择中位数作为基准元素。
• 使用三数取中法，即选择左端点、右端点和中间点的中位数作为基准元素。

2. 小数组使用插入排序

当递归到小数组时，插入排序比迅速排序更高效。通常情况下，当数组长度小于10时，可以考虑使用插入排序。

3. 避免递归

使用尾递归优化，降低递归调用的开销。

五、Java迅速排序的优化实现

以下是考虑了以上优化技巧的Java迅速排序实现代码：

public class QuickSortOptimized {
    private static final int INSERTION_SORT_THRESHOLD = 10;
    public static void quickSort(int[] arr, int left, int right) {
        if (left < right) {
            if (right - left < INSERTION_SORT_THRESHOLD) {
                insertionSort(arr, left, right);
            } else {
                int pivotIndex = partition(arr, left, right);
                quickSort(arr, left, pivotIndex - 1);
                quickSort(arr, pivotIndex + 1, right);
            }
        }
    }
    private static int partition(int[] arr, int left, int right) {
        int pivot = medianOfThree(arr, left, right);
        int i = left - 1;
        for (int j = left; j < right; j++) {
            if (arr[j] < pivot) {
                i++;
                swap(arr, i, j);
            }
        }
        swap(arr, i + 1, right);
        return i + 1;
    }
    private static int medianOfThree(int[] arr, int left, int right) {
        int center = (left + right) / 2;
        if (arr[left] > arr[center]) {
            swap(arr, left, center);
        }
        if (arr[left] > arr[right]) {
            swap(arr, left, right);
        }
        if (arr[center] > arr[right]) {
            swap(arr, center, right);
        }
        return arr[center];
    }
    private static void insertionSort(int[] arr, int left, int right) {
        for (int i = left + 1; i <= right; i++) {
            int temp = arr[i];
            int j;
            for (j = i; j > left && arr[j - 1] > temp; j--) {
                arr[j] = arr[j - 1];
            }
            arr[j] = temp;
        }
    }
    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    public static void main(String[] args) {
        int[] arr = {9, 5, 2, 7, 3, 6, 8};
        quickSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }
}

六、总结

迅速排序是一种高效的排序算法，其核心思想是分治法。通过递归地将大问题分解为小问题，迅速排序能够以O(n log n)的平均时间纷乱度完成排序任务。然而，在最坏情况下，迅速排序的时间纷乱度会退化到O(n^2)。为了优化迅速排序的性能，我们可以采用选择合适的基准元素、小数组使用插入排序、避免递归等策略。通过这些优化，我们可以使迅速排序在实际应用中表现更加出色。

本文由IT视界版权所有,禁止未经同意的情况下转发