求助：随机数据下快速排序实测复杂度异常为O(N²)的原因排查

我尝试绘制快速排序的理论时间复杂度与实测值对比图，输入递增、递减或常量数据序列时，快排曲线符合O(N²)预期，但输入随机数据流时出现问题。理论上随机数据下快速排序的时间复杂度为O(n log n)，但我的实测数据却显示为O(N²)。我已尝试不同分区实现，且确认元素可被正确排序。

以下是我的快速排序及分区步骤实现代码：

template<typename BidirectionalIterator, typename Compare>
BidirectionalIterator partition_impl(BidirectionalIterator first,
BidirectionalIterator last, Compare cmp) {
    auto pivot = std::prev(last, 1);
    if (first == pivot) return first;
    while (first != last) {
        while (cmp(*first, *pivot)) { ++first; } // search greater > pivot
        do { --last; } while (!cmp(*last, *pivot) && last >= first); // search < pivot
        if (first > last) {     // if left iterator has surpassed right iterator
            std::iter_swap(first, pivot);
            return first;
        }
        if (*first > *last) {
            std::iter_swap(first, last);
            ++first;
        }
    }
    std::iter_swap(first, pivot);
    return first;
}

template <typename FwdIt, typename Comp = std::less<>>
void quick_sort(FwdIt first, FwdIt last, Comp cmp = Comp{}) {
    if (std::distance(first, last) <= 1) return;

    FwdIt split = partition_impl(first, last, cmp);

    quick_sort(first, split, cmp);  // sorts the left partition
    quick_sort(split + 1, last, cmp);   // sorts the right partition
}

补充测量代码：

void measure(std::vector<int>& ds) {
    Timer::start();
    algo_ptr(ds.begin(), ds.end(), std::less<>());
    Timer::stop();
}
void collectSamples(data_series_t& data_series) {
    for (int k = 0; k < NUM_OF_SAMPLES; ++k) {
        auto ds = std::get<1>(data_series)(x_measurement_point);
        measure(ds);
        measurements.push_back(Timer::elapsedTime());
    }
}

注：algo_ptr指向上述快速排序实现，每个数据序列收集10个样本，每次迭代生成新随机序列以避免排序已有序元素。

你的快速排序实现存在几个关键问题，直接导致随机数据下时间复杂度退化为O(N²)：

1. 分区函数的迭代器停滞问题
   在partition_impl中，找到需要交换的first和last后，你仅在*first > *last时执行交换并移动first。但当*first等于*last时，既不交换也不移动迭代器，会导致循环无法有效推进，分区后的子数组无法被合理分割，最终递归深度剧增到O(N)，时间复杂度退化为O(N²)。正确逻辑应该是：交换后无论元素是否相等，都要移动first（或同时移动first和last），保证迭代器持续推进。

2. Pivot选择与分区逻辑不匹配
   你固定选择数组最后一个元素作为pivot，虽然随机数据下理论上平均能得到O(n log n)，但分区逻辑的错误会让pivot无法有效分割数组——比如当大量元素等于pivot时，迭代器停滞会让左/右子数组几乎没有缩小，递归次数直接拉满。

3. 递归调用的迭代器兼容性与逻辑问题
   split + 1的写法仅支持随机访问迭代器（比如std::vector的迭代器），不兼容双向迭代器（比如std::list）；更关键的是，如果分区后split位置错误，会导致右半部分递归的数组范围没有正确缩小，进一步加剧递归深度问题。

4. 分区循环的内存访问风险
   do { --last; } while (!cmp(*last, *pivot) && last >= first)中，先执行--last再判断last >= first，当last原本等于first时，会出现last < first的情况，此时访问*last属于非法内存操作，可能引发未定义行为，间接影响排序效率。

修正后的核心代码示例 #

修正分区函数

template<typename BidirectionalIterator, typename Compare>
BidirectionalIterator partition_impl(BidirectionalIterator first,
BidirectionalIterator last, Compare cmp) {
    auto pivot = std::prev(last);
    if (first == pivot) return first;

    while (true) {
        // 找到第一个不小于pivot的元素
        while (cmp(*first, *pivot)) {
            ++first;
        }
        // 找到第一个小于等于pivot的元素
        --last;
        while (cmp(*pivot, *last)) {
            if (last == first) break;
            --last;
        }

        if (first >= last) break;

        std::iter_swap(first, last);
        ++first;
    }

    std::iter_swap(first, pivot);
    return first;
}

修正递归调用

template <typename FwdIt, typename Comp = std::less<>>
void quick_sort(FwdIt first, FwdIt last, Comp cmp = Comp{}) {
    if (std::distance(first, last) <= 1) return;

    FwdIt split = partition_impl(first, last, cmp);

    quick_sort(first, split, cmp);
    // 使用std::next保证兼容所有双向迭代器
    quick_sort(std::next(split), last, cmp);
}

额外测量建议 #

• 确保随机序列生成的随机性：使用std::random_device配合std::mt19937生成数据，避免伪随机序列存在隐藏规律。
• 计时排除额外开销：测量时仅统计排序逻辑的时间，排除vector内存分配、数据拷贝等无关耗时。

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