快速排序可视化演示

算法简介

快速排序（Quick Sort）是一种高效的、基于**分治**思想的排序算法。它的核心步骤包括：

**选择基准值 (Pivot):** 从数组（或子数组）中选择一个元素作为基准。
**分区 (Partition):** 重新排列数组，使得所有小于基准值的元素移到基准值之前，所有大于基准值的元素移到基准值之后。分区结束后，基准值就位于其最终排序后的位置。
**递归/迭代处理子区间:** 对基准值左右两边的子数组（不包括基准值本身）重复以上步骤。

递归 vs 迭代实现

递归实现: 代码结构清晰，直接体现分治思想。利用函数调用栈来管理待排序的子区间。缺点是当递归深度过大时可能导致栈溢出。

迭代实现 (显式栈): 使用一个显式的栈（如 `std::stack` 或数组模拟的栈）来存储待排序子区间的边界，避免了函数调用栈溢出的风险，但代码相对递归版本稍显复杂。

本页面将同时演示这两种实现方式的分区和排序过程。

递归实现

递归调用栈

迭代实现 (显式栈)

显式栈

性能统计 & 控制面板

递归 - 比较: 0 迭代 - 比较: 0

递归 - 交换: 0 迭代 - 交换: 0

递归 - 最大深度: 0 迭代 - 最大栈大小: 0

速度: 中等

总体进度: 0%

×

快速排序 C++ 实现

递归版本

// 分区函数 (Lomuto partition scheme)
int partition(int arr[], int low, int high) {
    int pivot = arr[high]; // 选择最后一个元素作为基准
    int i = (low - 1); // 小于等于 pivot 区域的右边界索引

    for (int j = low; j <= high - 1; j++) {
        // 如果当前元素小于或等于 pivot
        if (arr[j] <= pivot) {
            i++; // 扩展小于区域
            std::swap(arr[i], arr[j]); // 交换到小于区域
        }
    }
    std::swap(arr[i + 1], arr[high]); // 将 pivot 放到正确位置
    return (i + 1); // 返回 pivot 的索引
}

// 快速排序主函数 (递归)
void quickSortRecursive(int arr[], int low, int high) {
    if (low < high) {
        // pi 是分区后基准值的索引
        int pi = partition(arr, low, high);

        // 分别对基准值左右两边的子数组进行排序
        quickSortRecursive(arr, low, pi - 1);
        quickSortRecursive(arr, pi + 1, high);
    }
}

迭代版本 (使用 std::stack)

// 包含必要的头文件
#include 
#include  // for std::pair

// 分区函数 (同上)
int partition(int arr[], int low, int high); // 假设 partition 函数已定义

// 快速排序主函数 (迭代)
void quickSortIterative(int arr[], int low, int high) {
    // 创建一个栈来存储子数组的起始和结束索引
    std::stackint, int>> st;

    // 将初始数组的范围压入栈
    st.push({low, high});

    // 当栈不为空时，持续处理
    while (!st.empty()) {
        // 弹出栈顶的子数组范围
        low = st.top().first;
        high = st.top().second;
        st.pop();

        // 执行分区操作
        int pi = partition(arr, low, high);

        // 如果左侧子数组存在，将其范围压栈
        if (pi - 1 > low) {
            st.push({low, pi - 1});
        }

        // 如果右侧子数组存在，将其范围压栈
        if (pi + 1 < high) {
            st.push({pi + 1, high});
        }
    }
}