快速排序

约 1767 字大约 6 分钟

2025-01-11

⭐ 题目日期：

百度 - 2024/1/7

🌳 题目描述：

快速排序

🕵🏽‍♂️ 面试评估：

这道题主要考察候选人对快速排序算法的理解，特别是在递归算法和分治策略上，候选人需要展现如何通过选择一个合适的枢轴元素将数组高效地划分为两个子数组，并递归地对这些子数组进行排序，在这过程中确定递归的终止条件，避免不必要的递归调用和数组操作，且正确理解并实现分区操作，确保枢轴元素最终处于正确的位置上。

🧗难度系数：

⭐️ ⭐️ ⭐️ ⭐️

📝思路分析：

快速排序（英语: Quick Sort）是一种高效的通用排序算法。它由英国计算机科学家Tony Hoare于1959年开发，并于1961年发表。至今，快速排序仍然是一种常用的排序算法。总体上，对于随机化数据，特别是较大的数据集，快速排序比归并排序和堆排序稍快一些。

快速排序是一种分治算法。它的工作原理如下：

选择基准值：首先从待排序的数组中选择一个元素作为基准值（pivot）。通常可以选择第一个元素、最后一个元素或者随机选择一个元素作为基准值。
分区操作：对数组进行分区（partition），使得比基准值小的元素都在基准值的左边，比基准值大的元素都在基准值的右边。经过分区操作后，基准值将数组分为了两部分，左边部分的元素都小于等于基准值，右边部分的元素都大于等于基准值。
递归排序：对分区后的左右两部分子数组分别重复上述步骤，即选择基准值、进行分区操作、递归排序，直到子数组的长度为 1 或 0，此时子数组已经有序，则整个数组有序，排序完成。

流程图如下：

💻代码(Java、Python、C++)：

Java

public List<List<Integer>> fourSum(int[] nums, int target) {
    List<List<Integer>> result = new ArrayList<>();

    // 如果数组为空或者数组长度小于 4,不可能满足四元组
    if (nums == null || nums.length < 4) {
        return result;
    }

    // 排序
    Arrays.sort(nums);

    int n = nums.length;

    // 遍历数组,最外层循环,固定第一个数,保证后面至少还剩三个数可以用
    for (int i = 0; i < n - 3; i++) {

        // 如果当前数与前一个数相同,跳过以避免重复
        if (i > 0 && nums[i] == nums[i - 1]) {
            continue;
        }

        // 如果 nums[i] 和接下来的三个最小数之和已经大于 target,则当前及后续的 i 都不可能满足条件,直接退出
        if ((long) nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) {
            break;
        }

        // 如果 nums[i] 和数组中最大的三个数之和小于 target，则当前 i 太小，跳过这个 i
        if ((long) nums[i] + nums[n - 3] + nums[n - 2] + nums[n - 1] < target) {
            continue;
        }

        // 遍历数组,内层循环,固定第二个数,保证后面至少还有两个数可以用
        for (int j = i + 1; j < n - 2; j++) {

            // 如果当前数与前一个数相同,跳过以避免重复
            if (j > i + 1 && nums[j] == nums[j - 1]) {
                continue;
            }

            // 如果当前组合的最小和大于 target,直接退出
            if ((long) nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target) {
                break;
            }

            // 如果当前组合的最大和小于 target,跳过这个 j
            if ((long) nums[i] + nums[j] + nums[n - 2] + nums[n - 1] < target) {
                continue;
            }

            // 双指针查找,确定第三个和第四个数, left 从 j + 1 开始向右搜索, right 从数组末尾 n - 1 开始向左搜索
            int left = j + 1;
            int right = n - 1;

            // 计算当前四元组的和 sum,并与目标值 target 进行比较
            while (left < right) {
                long sum = (long) nums[i] + nums[j] + nums[left] + nums[right];

                // 找到与 target 相等的组合,加入结果集
                if (sum == target) {
                    result.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));

                    // 跳过重复的左指针
                    while (left < right && nums[left] == nums[left + 1]) {
                        left++;
                    }

                    // 跳过重复的右指针
                    while (left < right && nums[right] == nums[right - 1]) {
                        right--;
                    }

                    // 移动指针
                    left++;
                    right--;
                } else if (sum < target) { // 如果 sum < target,说明当前和太小,左指针右移以增大和
                    left++;
                } else { // 如果 sum > target,说明当前和太大,右指针左移以减小和
                    right--;
                }
            }
        }
    }

    return result;
}

Python

def quick_sort(array):
    if not array:
        return array
    quick_sort_recursive(array, 0, len(array) - 1)
    return array

def quick_sort_recursive(array, left, right):
    if left >= right:
        return
    pivot_index = partition(array, left, right)
    quick_sort_recursive(array, left, pivot_index - 1)
    quick_sort_recursive(array, pivot_index + 1, right)

def partition(array, left, right):
    pivot = array[right]
    i = left
    j = right - 1
    while i <= j:
        if array[i] <= pivot:
            i += 1
        else:
            array[i], array[j] = array[j], array[i]
            j -= 1
    array[i], array[right] = array[right], array[i]
    return i

C++

#include <iostream>
#include <vector>
using namespace std;

class QuickSort {
public:
    vector<int> quickSort(vector<int>& array) {
        if (array.empty()) return array;
        quickSortRecursive(array, 0, array.size() - 1);
        return array;
    }

private:
    void quickSortRecursive(vector<int>& array, int left, int right) {
        if (left >= right) return;
        int pivotIndex = partition(array, left, right);
        quickSortRecursive(array, left, pivotIndex - 1);
        quickSortRecursive(array, pivotIndex + 1, right);
    }

    int partition(vector<int>& array, int left, int right) {
        int pivot = array[right];
        int i = left;
        int j = right - 1;
        while (i <= j) {
            if (array[i] <= pivot) {
                i++;
            } else {
                swap(array[i], array[j]);
                j--;
            }
        }
        swap(array[i], array[right]);
        return i;
    }

    void swap(int& a, int& b) {
        int temp = a;
        a = b;
        b = temp;
    }
};

🚵🏻复杂度分析：

性能分析：
- 时间复杂度
  - 最好情况：
    1. 当每次划分都能将数组分为两个大小相等的子数组时，时间复杂度为O(nlogn)。
    2. 这是因为每次划分都将问题规模减半，划分次数为logn（以 2 为底），而每次划分需要线性时间O(n)来处理子数组，所以总的时间复杂度为O(nlogn)。
  - 平均情况：
    1. 平均情况下，快速排序的时间复杂度也为O(nlogn)。
    2. 快速排序在平均情况下表现良好，因为它随机选择基准值的概率较大，使得划分相对均匀。
  - 最坏情况：
    1. 当每次划分都将数组分为一个非常小的子数组和一个非常大的子数组时，时间复杂度为O(n^2)。
    2. 例如，当数组已经有序或者逆序时，每次选择的基准值都是最小或最大的元素，导致划分极不均匀，需要进行O(n)次划分，每次划分需要O(n)的时间，所以总的时间复杂度为O(n^2)
- 空间复杂度
  - 快速排序的空间复杂度主要取决于递归调用的栈空间。
  - 最好情况和平均情况下，空间复杂度为logn，因为每次划分都能将问题规模减半，递归深度为logn。
  - 最坏情况（数组已经有序或逆序）下，空间复杂度为O(n)，因为每次划分都只能减少一个元素，递归深度为O(n)。
- 稳定性：快速排序是不稳定的排序算法。因为在分区过程中，如果有两个相等的元素，它们的相对顺序可能会因为分区而改变。