混合MSD基数排序+字符串快速排序的异常比较次数峰值问题

问题背景 #

我正在完成算法课程作业，主题是字符串排序算法。需要实现不同算法、统计字符比较次数、绘制图表并解释结果，其中MSD基数排序与字符串快速排序的混合算法的结果让我困惑：当待排序子数组规模小于某个阈值时，会使用针对字符串优化的快速排序变体替代基数排序。

实验结果 #

阈值为50时的表现 #

图表x轴为输入数组规模，y轴为对应规模下50个随机生成数组的平均比较次数。数组包含长度10-200的随机字符串（长度也随机），局部峰值出现在输入规模约3000处。

阈值为25时的表现 #

模式与阈值50时一致，但局部峰值出现在1500处。

该模式的特点是：相对较小的数组规模下，比较次数在特定大小处达到峰值；大输入规模下比较次数持续增长（这符合预期），但小输入的行为无法理解。

注意：基数排序是非比较排序，所有比较操作均由快速排序完成。最初推测是特定规模下快速排序频繁遇到最坏情况数组（时间复杂度达到O(n²)），但无法解释该现象的触发原因。

核心代码实现 #

MSD基数排序代码 #

struct RadixSortStep {
    size_t l;
    size_t r;
    size_t c;
};
void radix_sort(std::vector<std::string> &arr, CompCounter &cmp, bool sw) {
    std::queue<std::string> qs[allowed.size() + 1];
    std::queue<RadixSortStep> trace{};
    trace.push({0, arr.size() - 1, 0});

    while (!trace.empty()) {
        auto [l, r, c] = trace.front();
        trace.pop();
        if (l >= r) {
            continue;
        }
        if (sw && r - l <= threshold) {
            string_quick_sort(arr, cmp, l, r, c);
            continue;
        }

        for (size_t i = l; i <= r; ++i) {
            char sym = arr[i][c];
            auto ind = index(sym);
            auto &q = qs[ind];
            auto &s = arr[i];
            q.push(std::move(s));
        }

        size_t start = l;
        for (size_t i = 0; i <= allowed.size(); ++i ) {
            auto &q = qs[i];
            if (q.empty()) {
                continue;
            }

            size_t end = start + q.size() - 1;
            size_t j = start;
            while (!q.empty()) {
                arr[j++] = std::move(q.front());
                q.pop();
            }
            if (i != 0 && start < end) {
                trace.push(RadixSortStep{start, end, c + 1});
            }
            start = end + 1;
        }
    }
}

注：index函数接收char并返回其在允许符号数组中的索引，遵循ASCII表顺序，'\0'的索引为0，行为等价于将char转换为int。

初始字符串快速排序代码 #

void string_quick_sort(std::vector<std::string> &arr, CompCounter &cmp, size_t l, size_t r, size_t c) {
    if (l >= r) {
        return;
    }

    auto pivot = arr[l];
    bool short_pivot = pivot.size() == c;
    size_t el = l;
    size_t er = l;
    for (size_t k = l + 1; k <= r; ++k) {
        if (arr[k].size() == c) {
            if (short_pivot) {
                std::swap(arr[er + 1], arr[k]);
                ++er;
            } else {
                std::swap(arr[el], arr[k]);
                std::swap(arr[k], arr[er + 1]);
                ++el;
                ++er;
            }
        } else if (!short_pivot) {
            int cm = cmp.cmp(arr[k][c], pivot[c]);
            if (cm < 0) {
                std::swap(arr[el], arr[k]);
                std::swap(arr[k], arr[er + 1]);
                ++el;
                ++er;
            } else if (cm == 0) {
                std::swap(arr[er + 1], arr[k]);
                ++er;
            }
        }
    }

    if (el > 0) {
        string_quick_sort(arr, cmp, l, el - 1, c);
    }
    string_quick_sort(arr, cmp, er + 1, r, c);
    if (!short_pivot || l != el || r != er) {
        string_quick_sort(arr, cmp, el, er, c + 1);
    }
}

比较计数器实现 #

int CompCounter::cmp(char c1, char c2) {
    ++count;
    return c1 - c2;
}

CompCounter是工具类，通过count字段记录字符比较次数。

优化尝试与结果 #

按照建议修改快速排序实现，改用子数组中间元素或随机元素作为pivot：

static std::mt19937 gen(std::random_device{}());

void string_quick_sort(std::vector<std::string> &arr, CompCounter &cmp, size_t l, size_t r, size_t c) {
    if (l >= r) {
        return;
    }

//    auto pivot = arr[(r + l) / 2];  // <- 中间元素作为pivot

    // 随机pivot
    auto index = std::uniform_int_distribution<size_t>(l, r)(gen);
    auto pivot = arr[index];

    bool short_pivot = pivot.size() == c;
    size_t lt = l;
    size_t eq = l;
    size_t gt = r;

    while (eq <= gt) {
        if (arr[eq].size() == c) {
            if (short_pivot) {
                ++eq;
            } else {
                std::swap(arr[eq++], arr[lt++]);
            }
        } else if (short_pivot) {
            std::swap(arr[eq], arr[gt--]);
        } else { // if (!short_pivot)
            int cm = cmp.cmp(arr[eq][c], pivot[c]);
            if (cm < 0) {
                std::swap(arr[eq++], arr[lt++]);
            } else if (cm == 0) {
                ++eq;
            } else { // if (cm > 0)
                std::swap(arr[eq], arr[gt--]);
            }
        }
    }

    if (lt > 0) {
        string_quick_sort(arr, cmp, l, lt - 1, c);
    }
    string_quick_sort(arr, cmp, gt + 1, r, c);
    if (!short_pivot || l != lt || r != gt) {
        string_quick_sort(arr, cmp, lt, gt, c + 1);
    }
}

两种实现的结果几乎一致：模式和局部峰值完全相同，仅绝对比较次数略有增加。阈值为50时使用随机pivot的图表如下：

这说明峰值模式与快速排序最坏情况无关，现在我更加困惑了。

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