手撕快速排序

手撕快速排序

一、快速排序思想

快速排序通过选择一个基准元素，将数组分为两部分，使得左边所有元素小于基准，右边所有元素大于基准，然后递归地对这两部分进行排序。

二、快速排序实现的简易代码

#include <bits/stdc++.h>
using namespace std;

// 快速排序函数
void quicksort(vector<int> &nums, int l, int r)
{
    // 递归终止条件：左索引大于或等于右索引
    if (l >= r)
    {
        return;
    }
    
    // 初始化指针
    int i = l - 1; // 左指针
    int j = r + 1; // 右指针
    int p = nums[l]; // 选择基准元素

    // 分区过程
    while (i < j)
    {
        // 从左边找第一个大于或等于基准的元素
        do
        {
            ++i;
        } while (nums[i] < p);
        
        // 从右边找第一个小于或等于基准的元素
        do
        {
            --j;
        } while (nums[j] > p);
        
        // 交换找到的元素
        if (i < j)
        {
            swap(nums[i], nums[j]);
        }
    }

    // 递归对分区后的左右两部分进行排序
    quicksort(nums, l, j);
    quicksort(nums, j + 1, r);
}

int main()
{
    // 初始化待排序数组
    vector<int> nums = {1, 2, 1, 3, 4, 6, 5, 21, 6, 38, 24, 26262, 1241};

    // 调用快速排序
    quicksort(nums, 0, nums.size() - 1);
    
    // 输出排序结果
    for (auto n : nums)
    {
        cout << n << ' ';
    }
    return 0;
}

输出排序结果：

总结

快速排序是一种高效的排序算法，采用分治的思想

时间复杂度

• 最佳情况：O(n log n)（基准元素每次均匀分割）
• 平均情况：O(n log n)
• 最坏情况：O(n²)（当数组已经是有序的，或所有元素相同，且每次选择的基准是最小或最大值）
  空间复杂度
• 空间复杂度：O(log n)（递归调用栈的空间，取决于递归深度）
• 在最坏情况下（O(n)）时，可能需要额外的O(n)空间（当分区极不均匀时）