leetcode leetcode 排序 快速排序 分治

双路快速排序

分区原理与 LeetCode 笔记

Posted by BY on April 26, 2026
CATALOG

    原始笔记简短地写了”双路快排”，主体是一份带调试输出的代码。这里把分区原理与边界条件补上，代码保留原样。

    题目背景

    快速排序是基于分治的内部排序算法，平均时间复杂度 O(n log n)，最坏 O(n^2)。”双路快排”是它的一种常见优化变体，用两个指针从区间两端向中间扫描，能较好处理含有大量重复元素的输入。

    概念解释

    • 基准（pivot）：分区时被参照的那个元素，所有比它小的放左边、比它大的放右边。
    • 闭区间扫描：本笔记里 i、j 都是闭区间下标，循环条件 i <= j 中包含等号。原代码注释里也专门提示”此处还是要还有=号的，闭区间”。
    • 稳定性：快排不是稳定排序，相同元素的相对顺序可能改变。

    实现原理

    find_num(nums, i, j) 完成一轮分区：

    1. 取最左端元素 nums[k]（k = i）作为基准。
    2. 双指针 i（已自增过一次）、j 同时向中间靠拢：
      • 右指针 j 向左跳过所有 >= pivot 的元素；
      • 左指针 i 向右跳过所有 <= pivot 的元素；
      • 当两边都停下且仍 i < j 时，交换 nums[i] 与 nums[j]，再各前进/后退一格。
    3. 循环结束后，j 指向最后一个 <= pivot 的位置，把基准 nums[k] 与 nums[j] 互换，使基准就位。
    4. 返回基准的最终位置 j。

    quick_sort 拿到分割点 k 后，对 [i, k-1] 与 [k+1, j] 两个子区间分别递归即可。平均 O(n log n)，原地无需额外空间（递归栈 O(log n)）。

    备注：代码里保留了一些 std::cout 调试输出，用于当时定位边界问题，可在使用时直接删掉。

    参考实现

    双路快排。。

int find_num(vector<int>& nums, int i , int j)
{
    // std::cout << "i1=" <<  i << " j1 = " << j << std::endl;
    if(i >= j)
    {
        return j;
    }
    int k = i++;
    // ++i;
    std::cout << "k " << k << std::endl;
    while( i <= j)
    //此处还是要还有=号的，闭区间
    {
        // std::cout << i << " " << j << std::endl;
        while(i <= j && nums[j] >= nums[k])
        //此处还是要还有=号的，闭区间
        {
            --j;
        }
        while(i <= j && nums[i] <= nums[k])
        //此处还是要还有=号的，闭区间
        {
            ++i;
        }
        if(i < j)
        {
            int tt = nums[i];
            nums[i] = nums[j];
            nums[j] = tt;
            ++i;
            --j;
        }
    }
    // std::cout << j << std::endl;
    if(k < j )
    {
        // std::cout << "k "  << k << " j " << j << std::endl;
        int tt = nums[k];
        nums[k] = nums[j];
        nums[j] = tt;
    }
    //返回第j个位置
    return j;
}

void quick_sort(std::vector<int>& nums, int i , int j)
{
    int k = find_num(nums,i,j);
    // std::cout << "k " << k << std::endl;
    // if()
    if(i < k - 1)
    {
        // std::cout << "first" << k << std::endl;
        quick_sort(nums,i,k-1);
    }
    if(k + 1 < j)
    {
        // std::cout << "second" << k << std::endl;
        quick_sort(nums,k+1,j);
    }

}
    FEATURED TAGS
    Git Cheat Sheet Markdown Tools C++ Linker Thread Linux TCP Network GDB Debug leetcode 链表 WSL Ubuntu Windows Linux Kernel GCC Android adb Troubleshooting Profiling Sanitizer glibc MySQL Database Python curl Build ELF clang-format CMake Graphviz Performance vcpkg Protobuf 排查 速查 内存 STL 调试 性能分析 性能 读书笔记 方法论 架构 网络 Timer mbedTLS TLS 安全 负载均衡 脚本 工具 LRU 二叉树 BST 中序遍历 回溯 二分查找 优先队列 排序 旋转数组 jenkins 部署
    FRIENDS