快速排序Java时间复杂度

### Java 中快速排序的时间复杂度分析

#### 平均情况下的时间复杂度
快速排序的平均时间复杂度为 \(O(n \log n)\)[^1]。这一结论基于每次划分操作能够大致均匀地分割待排序序列的理想假设。

#### 最坏情况下的时间复杂度
然而，在最糟糕的情况下——即每当选择的基准元素总是最大或最小值时，快速排序会退化成近乎线性的性能表现，此时其时间复杂度上升至 \(O(n^2)\)。这种极端情形通常发生在已经有序的数据集上执行未优化版本的快速排序算法时。

#### 实现细节影响
具体实现方式也会影响实际运行效率。例如，在Java中定义递归函数 `quicksort(int[] arr, int left, int right)` 来完成排序过程[^2]。为了提高稳定性并减少最坏情况下发生的概率，可以选择更优策略选取枢轴（pivot），比如采用三数取中法或其他随机化技术。

public class QuickSortExample {
    public static void quicksort(int[] arr, int low, int high) {
        if (low < high) {
            // pi is partitioning index
            int pi = partition(arr, low, high);

            // Recursively sort elements before and after partition
            quicksort(arr, low, pi - 1);
            quicksort(arr, pi + 1, high);
        }
    }

    private static int partition(int[] array, int low, int high) {
        int pivot = array[high];
        int i = (low - 1); // Index of smaller element

        for (int j = low; j <= high - 1; j++) {
            // If current element is smaller than the pivot
            if (array[j] < pivot) {
                i++;

                // swap array[i] and array[j]
                int temp = array[i];
                array[i] = array[j];
                array[j] = temp;
            }
        }

        // swap array[i+1] and array[high] (or pivot)
        int temp = array[i + 1];
        array[i + 1] = array[high];
        array[high] = temp;

        return i + 1;
    }
}