快速排序（Quick Sort）

快速排序是应用最广泛的排序算法之一，采用**分治法（Divide and Conquer）**策略：每次选择一个“基准元素”将数组划分为左右两部分，然后递归排序左右两侧子数组。

由于其平均时间复杂度为 O(n log n)、原地排序、常数因子小，在大多数实际应用中性能优于归并排序与堆排序。

📌 算法原理解释

快速排序的核心流程如下：

1. 选定一个基准（pivot），通常是当前子数组的第一个、最后一个或中间值；
2. 将数组划分为两部分：小于等于基准值的放左边，大于的放右边；
3. 对左右两部分分别递归执行快速排序；
4. 最终组合结果。

例如数组 [6, 3, 8, 5, 2]，以 6 为基准：

• 小于6的：[3, 5, 2]
• 大于6的：[8]
• 合并为 [2, 3, 5, 6, 8]

💻 多语言代码实现

javascript

// JavaScript 快速排序
function quickSort(arr) {
  if (arr.length <= 1) return arr;

  const pivot = arr[0];
  const left = arr.slice(1).filter(x => x <= pivot);
  const right = arr.slice(1).filter(x => x > pivot);

  return [...quickSort(left), pivot, ...quickSort(right)];
}

python

# Python 快速排序
def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[0]
    left = [x for x in arr[1:] if x <= pivot]
    right = [x for x in arr[1:] if x > pivot]
    return quick_sort(left) + [pivot] + quick_sort(right)

cpp

// C++ 快速排序（原地）
#include <vector>
using namespace std;

void quickSort(vector<int>& arr, int left, int right) {
    if (left >= right) return;
    int pivot = arr[left], i = left, j = right;
    while (i < j) {
        while (i < j && arr[j] >= pivot) j--;
        arr[i] = arr[j];
        while (i < j && arr[i] <= pivot) i++;
        arr[j] = arr[i];
    }
    arr[i] = pivot;
    quickSort(arr, left, i - 1);
    quickSort(arr, i + 1, right);
}

java

// Java 快速排序
public class QuickSort {
    public static void quickSort(int[] arr, int left, int right) {
        if (left >= right) return;
        int pivot = arr[left], i = left, j = right;
        while (i < j) {
            while (i < j && arr[j] >= pivot) j--;
            arr[i] = arr[j];
            while (i < j && arr[i] <= pivot) i++;
            arr[j] = arr[i];
        }
        arr[i] = pivot;
        quickSort(arr, left, i - 1);
        quickSort(arr, i + 1, right);
    }
}

php

<?php
// PHP 快速排序
function quickSort(array $arr): array {
    if (count($arr) <= 1) return $arr;

    $pivot = $arr[0];
    $left = array_filter(array_slice($arr, 1), fn($x) => $x <= $pivot);
    $right = array_filter(array_slice($arr, 1), fn($x) => $x > $pivot);

    return array_merge(quickSort($left), [$pivot], quickSort($right));
}
?>

go

// Go 快速排序
package main

func quickSort(arr []int) []int {
    if len(arr) <= 1 {
        return arr
    }
    pivot := arr[0]
    left, right := []int{}, []int{}
    for _, v := range arr[1:] {
        if v <= pivot {
            left = append(left, v)
        } else {
            right = append(right, v)
        }
    }
    left = quickSort(left)
    right = quickSort(right)
    return append(append(left, pivot), right...)
}

✅ 算法特点与总结

属性	描述
时间复杂度	平均 O(n log n)，最坏 O(n²)（已排序时最差）
空间复杂度	O(log n)（递归栈）或 O(n)（函数式写法）
稳定性	❌ 不稳定
是否原地排序	✅ 可实现原地排序（如 C++/Java 实现）

⚠️ 提示：快速排序虽然最坏时间复杂度是 O(n²)，但在实际中非常高效，建议搭配“三数取中”或随机基准优化其稳定性。