Java 快速排序算法实现详解

以下是一个简单的 Java 快速排序算法实现：

public class QuickSort {
    public static void main(String[] args) {
        int[] arr = { 7, 5, 6, 2, 1, 3, 9, 8, 4 };
        quickSort(arr, 0, arr.length - 1);
        for (int i : arr) {
            System.out.print(i + " ");
        }
    }

    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);
        }
    }

    public static int partition(int[] arr, int left, int right) {
        int pivotValue = arr[right];
        int pivotIndex = left;
        for (int i = left; i < right; i++) {
            if (arr[i] < pivotValue) {
                swap(arr, i, pivotIndex);
                pivotIndex++;
            }
        }
        swap(arr, pivotIndex, right);
        return pivotIndex;
    }

    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

快速排序算法原理

快速排序算法是一种分治算法，其基本思想是：

1. **选择一个基准元素（pivot）：**通常选择数组的最后一个元素作为基准元素。
2. 分区操作： 将数组划分为两个子数组，左子数组的所有元素都小于基准元素，右子数组的所有元素都大于或等于基准元素。
3. 递归排序： 对左子数组和右子数组分别进行快速排序。

代码解析

• quickSort(arr, left, right) 方法：递归排序函数，对数组 arr 的 left 到 right 部分进行排序。
• partition(arr, left, right) 方法：分区操作，将数组 arr 的 left 到 right 部分划分为两个子数组。
• swap(arr, i, j) 方法：交换数组 arr 中 i 和 j 位置的元素。

总结

快速排序算法是一种高效的排序算法，其平均时间复杂度为 O(n log n)，最坏时间复杂度为 O(n^2)。在实际应用中，快速排序算法被广泛使用，例如在数据库系统中对数据进行排序。

更多信息

• 快速排序算法维基百科
• 快速排序算法动画演示