C++中const unsigned**类型指针的快速排序实现疑问

先搞懂const unsigned**的含义 #

别被多层指针的const搞晕，这个类型的层级拆解很关键：

• 最内层的const unsigned：表示最终指向的a数组元素不可修改，也就是**begin不能赋值，这完全符合a数组不可修改的要求
• 中间层的const unsigned*：这是b数组存储的指针类型，这个指针本身可以自由修改（我们要排序的就是这些指针在b数组里的位置）
• 最外层的const unsigned**：这是指向b数组元素的指针，本身也可以修改（比如用来遍历数组）

所以核心结论是：你完全可以交换b数组里的指针，只要不去触碰**x（a的元素）就行。

错误根源：你的swap操作碰了a的元素 #

你之前错误修改**a，肯定是swap的时候写了类似swap(**x, **y)的代码——这是直接交换a数组的元素，当然会触发const限制。正确的swap应该交换的是b数组里的指针本身，也就是*x和*y。

比如正确的swap函数：

void swap(const unsigned** x, const unsigned** y) {
    const unsigned* temp = *x;
    *x = *y;
    *y = temp;
}

这里操作的是*x和*y，也就是b数组里的两个指针变量，完全没碰a的元素，符合const要求。

快速排序的实现示例 #

基于这个swap，我们可以实现符合要求的quicksort：

void quicksort(const unsigned** begin, const unsigned** end) {
    // 递归终止条件：区间长度小于等于1，无需排序
    if (end - begin <= 1) {
        return;
    }

    // 选基准：取区间中间位置的指针指向的a元素值
    const unsigned** pivot_ptr = begin + (end - begin) / 2;
    const unsigned pivot_val = **pivot_ptr;
    // 把基准指针移到区间末尾，方便后续分区操作
    swap(pivot_ptr, end - 1);
    const unsigned** store_ptr = begin;

    // 分区：遍历区间，将指向元素值小于基准的指针移到左侧
    for (const unsigned** curr = begin; curr < end - 1; ++curr) {
        if (**curr < pivot_val) {
            swap(curr, store_ptr);
            ++store_ptr;
        }
    }
    // 把基准指针移到分区后的正确位置
    swap(store_ptr, end - 1);

    // 递归排序左右两个子区间
    quicksort(begin, store_ptr);
    quicksort(store_ptr + 1, end);
}

验证测试代码 #

你可以用这段代码验证逻辑，确保a数组未被修改，b数组指针按指向值排序：

#include <iostream>

// 上面的swap和quicksort函数放在这里

int main() {
    const unsigned a[] = {5, 2, 9, 1, 5, 6};
    const unsigned* b[] = {&a[0], &a[1], &a[2], &a[3], &a[4], &a[5]};

    std::cout << "排序前b指针指向的值：";
    for (auto p : b) {
        std::cout << *p << " ";
    }
    std::cout << "\n";

    quicksort(std::begin(b), std::end(b));

    std::cout << "排序后b指针指向的值：";
    for (auto p : b) {
        std::cout << *p << " ";
    }
    std::cout << "\n";

    return 0;
}

内容的提问来源于stack exchange，提问作者A02