java写出快速排序算法

作为一名热衷于算法研究的程序员，我经常沉浸在各种排序算法的海洋中。今天，我想与大家分享一种既高效又广泛应用的排序算法——快速排序。快速排序由C. A. R. Hoare在1960年提出，它以其分而治之的思想和优异的平均性能而闻名。快速排序的基本思想是选择一个基准值，然后将数组分为两部分，一部分包含所有小于基准值的元素，另一部分包含所有大于基准值的元素。这个过程递归地应用于两个子数组，直到整个数组有序。

快速排序的定义与条件

快速排序是一种分而治之的排序算法，它通过选择一个元素作为基准（pivot），然后重新排列数组，使得所有比基准值小的元素都在基准的左边，所有比基准值大的元素都在基准的右边。这个过程称为分区（partitioning）。之后，递归地将这个过程应用于基准左边和右边的子数组。

快速排序与其它排序算法的对比

快速排序在平均情况下的性能非常出色，但最坏情况下的性能会退化到 (O(n^2))。相比之下，归并排序在最坏情况下也能保持 (O(n \log n)) 的时间复杂度，但需要额外的 (O(n)) 空间。堆排序则在空间复杂度上有优势，但同样不稳定。

核心类与方法

快速排序算法的核心在于partition方法，它负责将数组分为两部分，并返回基准值的正确位置。递归调用快速排序本身是另一个关键步骤。

使用场景

快速排序适用于大多数需要排序的场景，尤其是当数据集较大且基本有序时。它在内部排序中非常高效，但在数据集很小或者完全逆序时，性能可能不如其他算法。

代码案例

以下是两个快速排序的Java代码示例。

示例1：基本的快速排序实现

public class QuickSort {
    public void sort(int[] arr, int low, int high) {
        if (low < high) {
            int pivotIndex = partition(arr, low, high);
            sort(arr, low, pivotIndex - 1);
            sort(arr, pivotIndex + 1, high);
        }
    }

    private int partition(int[] arr, int low, int high) {
        int pivot = arr[high];
        int i = (low - 1);
        for (int j = low; j < high; j++) {
            if (arr[j] < pivot) {
                i++;
                swap(arr, i, j);
            }
        }
        swap(arr, i + 1, high);
        return i + 1;
    }

    private 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 = {10, 7, 8, 9, 1, 5};
        QuickSort quickSort = new QuickSort();
        quickSort.sort(arr, 0, arr.length - 1);
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

示例2：随机化快速排序

为了避免最坏情况的发生，我们可以通过随机选择基准值来实现随机化快速排序。

import java.util.Random;

public class RandomizedQuickSort {
    public void sort(int[] arr, int low, int high) {
        if (low < high) {
            int k = randomPivotPartition(low, high);
            sort(arr, low, k - 1);
            sort(arr, k + 1, high);
        }
    }

    private int randomPivotPartition(int low, int high) {
        Random rand = new Random();
        int pivotIndex = low + rand.nextInt(high - low);
        swap(arr, pivotIndex, high);
        return partition(arr, low, high);
    }

    private int partition(int[] arr, int low, int high) {
        int pivot = arr[high];
        int i = (low - 1);
        for (int j = low; j < high; j++) {
            if (arr[j] < pivot) {
                i++;
                swap(arr, i, j);
            }
        }
        swap(arr, i + 1, high);
        return i + 1;
    }

    private 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 = {10, 7, 8, 9, 1, 5};
        RandomizedQuickSort randomizedQuickSort = new RandomizedQuickSort();
        randomizedQuickSort.sort(arr, 0, arr.length - 1);
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

总结

快速排序是一种非常强大的排序算法，它在实际应用中表现出色，尤其是当数据集较大时。通过随机化选择基准值，我们可以进一步优化算法，避免最坏情况的发生。希望这两个代码示例能够帮助你更好地理解和实现快速排序算法。