java快速排序的两种方法

快速排序，作为排序算法中的佼佼者，以其平均时间复杂度为O(n log n)而广受青睐。我初次接触快速排序时，被其递归的思维方式和高效的性能所吸引。快速排序不仅在理论上性能优越，在实际应用中也表现出色，尤其是在处理大数据集时。它是一种分而治之的策略，通过选取基准值将数据分为两部分，然后递归地在这两部分上执行排序操作。

快速排序的两种实现方法

原地快速排序（In-Place Quick Sort）

原地快速排序是一种在原数组上进行排序的方法，不需要额外的存储空间。它通过选取一个元素作为“基准”（pivot），然后重新排列数组，使得所有比基准小的元素都在基准的左边，所有比基准大的元素都在基准的右边。这个过程称为分区（partitioning）。之后，递归地对基准左边和右边的子数组进行同样的操作。

非原地快速排序（Non-In-Place Quick Sort）

与原地快速排序不同，非原地快速排序需要额外的存储空间来存储排序过程中的元素。这种方法通常使用辅助数据结构，如链表或栈，来存储排序过程中的子数组。虽然这种方法在空间复杂度上不如原地快速排序高效，但在某些特定情况下，如需要稳定排序或处理链表数据时，它可能更为适用。

对比表格

核心类与方法

在Java中，快速排序可以通过多种方式实现。以下是两种实现的核心类和方法：

原地快速排序

public class InPlaceQuickSort {
    public void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            int pivotIndex = partition(arr, low, high);
            quickSort(arr, low, pivotIndex - 1);
            quickSort(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;
    }
}

非原地快速排序

import java.util.LinkedList;
import java.util.List;

public class NonInPlaceQuickSort {
    public void quickSort(List<Integer> list) {
        if (list.size() <= 1) {
            return;
        }
        int pivot = list.get(0);
        List<Integer> less = new LinkedList<>();
        List<Integer> greater = new LinkedList<>();

        for (int num : list) {
            if (num < pivot) {
                less.add(num);
            } else if (num > pivot) {
                greater.add(num);
            }
        }

        quickSort(less);
        list.clear();
        list.addAll(less);
        list.add(pivot);
        list.addAll(greater);
    }
}

使用场景

原地快速排序适用于需要在原数组上进行排序且对空间复杂度有较高要求的场景。例如，在嵌入式系统或内存受限的环境中，原地快速排序可以节省大量的内存空间。

非原地快速排序适用于需要稳定性排序的场景，或者当数据存储在非数组结构（如链表）中时。例如，在数据库系统中，可能需要保持元素的原始顺序，这时非原地快速排序就非常有用。

结语

快速排序是一种强大的排序算法，它在各种编程语言和应用中都有广泛的使用。通过理解其两种实现方式——原地和非原地——我们可以根据不同的需求和场景选择合适的排序方法。无论是在学术研究还是在工业应用中，快速排序都是一个值得深入学习和掌握的算法。