排序算法内省排序（STL sort） IntroSort --C/C++

2024-08-12 11:33 由 HJfjfK 发表于 #其他

内观排序/内省排序

内省排序 - 维基百科，自由的百科全书 (wikipedia.org)

内省排序（英语：Introsort）是由大卫·穆塞尔在1997年设计的排序算法。这个排序算法首先从快速排序开始，当递归深度超过一定深度（深度为排序元素数量的对数值）后转为堆排序。采用这个方法，内省排序既能在常规数据集上实现快速排序的高性能，又能在最坏情况下仍保持𝑂(𝑛log⁡𝑛)的时间复杂度。由于这两种算法都属于比较排序算法，所以内省排序也是一个比较排序算法。

在快速排序算法中，一个关键操作就是选择基准点（Pivot）：元素将被此基准点分开成两部分。最简单的基准点击择算法是使用第一个或者最后一个元素，但这在排列已部分有序的序列上性能很糟。尼克劳斯·维尔特为此设计了一个快速排序的变体，使用处于中间的元素来防止在某些特测序列上性能退化为𝑂(𝑛2)的状况。这个3基准中位数选择算法从序列的第一，中间和最后一个元素获取中位数来作为基准，虽然这个算法在现实世界的数据上性能表现良好，但经过精心设计的“破解序列”仍能大幅降低此变体算法的性能。这样就有攻击者精心设计序列发送到因特网服务器以进行拒绝服务（DoS）攻击的潜在可能性。

穆塞尔研究指出，在针对3基准中位数选择算法设计的100,000个元素的“破解序列”上，内省排序的运行时间是这种3基准快速排序的1 / 200。在穆塞尔的算法中，最终较小范围内数据的排序由罗伯特·塞奇威克提出的小数据排序算法完成。

在2000年6月，SGI的C++标准模板库的stl_algo.h （页面存档备份，存于互联网档案馆）中的不稳定排序算法采用了穆塞尔的内省排序算法。在此实现中，切换到插入排序的数据量阈值为16个。

内观排序_百度百科 (baidu.com)

在实践中，快速排序的速度很快的，不足的地方是在某些情况下，速度会很慢。原因是切分原素选取不合理，使得切分出来的两个问题大小不对称，子问题太多，深度太深。一个可行的改进是，选三个元素，然后取中间的一个作为切分元素，这样效果会好些，但是仍然会有一些极端的情况会使得算法退化为平方。只要这三个元素是可以预计的，都能设计出让算法退化的输入。另一个改进方案是，选一个随机数。假设随机数发生器比较随机。但是只产生一个随机数，切分出来的效果还是不会很好，多产生几个随机数，再选中间数，效果会好些，只是产生随机数的过程本身就耗时，所以不能产生太多。

有些算法不用随机数，也能确保算法不会退化到平方。但是在实践中，这些算法速度很慢。

内观排序，即把快速排序跟堆排序结合起来。堆排序是很稳定的，不会退化，只是一般情况下比较慢。在快速排序t算法出现退化的情况下，再调用堆排序。问题是怎么判断退化。一种简单的方案是，当深度超过某值的时候，根据经验，这个值可以设为2*lgN。直接调用堆排序对切分后的子问题进行排序。

这个算法在平均情况下，跟快速排序差不多，在最坏情况下，比快速排序要快一个数量级。

C++ Standard Template Library (STL) 中的 std::sort 函数使用的排序算法是 Introspective Sort（简称 introsort 或 intro sort），这是一种混合排序算法。Introsort 结合了快速排序、堆排序和插入排序的特点，旨在提供良好的平均性能和最坏情况性能保证。

Introsort 的工作原理：

快速排序：

Introsort 开始时使用快速排序算法进行排序。

快速排序具有很好的平均性能，但最坏情况下性能会退化至 O(n²)。

深度检测与切换到堆排序：

为了避免快速排序最坏情况的发生，Introsort 会监控递归的深度。

如果递归深度超过了某个阈值（通常是 2 * log₂(n)），它会切换到堆排序。

堆排序具有 O(n log n) 的最坏情况性能，这可以防止性能退化。

插入排序：

对于小数组，Introsort 可能会切换到插入排序。

插入排序对于小数组非常高效，通常当数组大小低于某个阈值时使用。

总结：

优点：Introsort 结合了快速排序的高速度与堆排序的最坏情况性能保证，同时利用插入排序来优化小数组的处理。

时间复杂度：平均情况和最坏情况的时间复杂度均为 O(n log n)。

空间复杂度：由于使用递归，Introsort 的空间复杂度为 O(log n)。

稳定性：Introsort 不是稳定的排序算法，这意味着相等的元素之间的相对顺序可能不会被保留。

#include <algorithm>
#include <vector>
#include <cassert>

// Partition function for quicksort
template<typename RandomAccessIterator, typename Compare>
RandomAccessIterator partition(RandomAccessIterator first, RandomAccessIterator last, Compare comp) {
    auto pivot = *last;
    auto i = first - 1;
    for (auto j = first; j != last; ++j) {
        if (comp(*j, pivot)) {
            ++i;
            std::swap(*i, *j);
        }
    }
    std::swap(*(i+1), *last);
    return i + 1;
}

// Introsort implementation
template<typename RandomAccessIterator, typename Compare>
void introsort(RandomAccessIterator first, RandomAccessIterator last, Compare comp, int depth_limit) {
    auto size = last - first;
    if (size < 16) {
        // Insertion sort for small subarrays
        std::sort(first, last, comp);
    } else if (depth_limit == 0) {
        // Switch to heapsort
        std::make_heap(first, last, comp);
        std::sort_heap(first, last, comp);
    } else {
        auto pivot = partition(first, last, comp);
        introsort(first, pivot, comp, depth_limit - 1);
        introsort(pivot + 1, last, comp, depth_limit - 1);
    }
}

// Wrapper function for introsort
template<typename RandomAccessIterator, typename Compare>
void introsort(RandomAccessIterator first, RandomAccessIterator last, Compare comp) {
    auto size = last - first;
    auto depth_limit = 2 * std::log(size);
    introsort(first, last, comp, depth_limit);
}

// Example usage
int main() {
    std::vector<int> vec = {5, 3, 8, 4, 2, 7, 1, 6};
    
    // Use introsort with default comparison
    introsort(vec.begin(), vec.end(), std::less<int>());
    
    // Check the sorted vector
    assert(std::is_sorted(vec.begin(), vec.end()));
    
    for (int num : vec) {
        std::cout << num << " ";
    }
    
    return 0;
}

内省排序中的堆排序作用

在 Introsort（Introspective Sort）中使用堆排序的原因主要是为了确保最坏情况下的性能。快速排序在平均情况下非常高效，但它的最坏情况性能可以退化到 O(n²)，这通常发生在输入数据已经部分排序或者选择的枢轴总是最差的选择时。为了避免这种情况，Introsort 在递归深度达到一定阈值时切换到堆排序，这样即使在最坏情况下也能保证 O(n log n) 的时间复杂度。

堆排序的好处：

最坏情况性能保证：

堆排序的时间复杂度在最坏情况下也是 O(n log n)，这使得 Introsort 即使在处理最不利的输入数据时也能保持高效。

简单性：

堆排序算法相对简单，易于实现，尤其是在 C++ 标准库中已经提供了现成的函数，如 std::make_heap 和 std::sort_heap。

无需额外存储空间：

堆排序是原地排序算法，除了几个辅助变量外不需要额外的存储空间。这使得它适用于内存受限的环境。

稳定性：

虽然堆排序本身不是稳定的排序算法，但在 Introsort 的上下文中，这并不是一个问题，因为快速排序本身也不稳定。

在 Introsort 中的具体作用：

避免快速排序的最坏情况：

通过监测快速排序的递归深度，一旦达到预定的最大深度，Introsort 就会切换到堆排序。这可以防止快速排序因最坏情况输入而导致性能急剧下降。

提供性能保障：

堆排序的最坏情况性能保证确保了 Introsort 在任何情况下都不会退化到 O(n²) 的性能。

高效处理剩余数据：

通常在递归深度达到阈值时，快速排序已经完成了大部分排序工作。此时堆排序只需要处理剩余的部分未排序数据，这通常比从头开始排序整个数组要快得多。

如何在 Introsort 中使用堆排序：

设置最大递归深度：

通常设置为 2 * log₂(n)，其中 n 是待排序数组的长度。

监测递归深度：

在递归调用快速排序的过程中，不断更新递归深度计数器。

切换到堆排序：

一旦递归深度达到最大值，就停止使用快速排序，并通过以下步骤应用堆排序：

使用 std::make_heap 将数组转换成一个大顶堆或小顶堆。

使用 std::sort_heap 完成排序。

示例代码中的堆排序部分：
if (depth_limit == 0) {
  // Switch to heapsort
  std::make_heap(first, last, comp);  // Convert the range into a heap
  std::sort_heap(first, last, comp);  // Sort the heap in-place
}
这里，std::make_heap 创建了一个大顶堆，而 std::sort_heap 则对堆进行排序，得到最终的有序数组。

综上所述，Introsort 中使用堆排序的主要目的是为了确保在最坏情况下仍能保持 O(n log n) 的时间复杂度，从而提供可靠的性能保证

内省排序中插入排序(小区间优化)部分

在 Introsort（Introspective Sort）中使用插入排序是为了优化小规模数组的排序过程。插入排序是一种简单的排序算法，它在处理小数组时非常高效。在 Introsort 中，当子数组的大小小于一个预定义的阈值时，就会使用插入排序来替代快速排序。这样做有几个好处：

减少递归开销：

对于小数组，使用插入排序可以减少快速排序的递归调用次数，从而降低递归带来的栈空间占用和函数调用开销。

提高效率：

插入排序对于小数组来说是非常高效的，尤其是当数组已经部分排序时。因此，在 Introsort 中，对于小规模子数组使用插入排序可以显著提高性能。

简化实现：

插入排序的实现非常简单，不需要复杂的逻辑或额外的数据结构，这使得它很容易集成到 Introsort 中。

插入排序的工作原理：

插入排序的基本思想是将数组分成已排序部分和未排序部分。初始时，已排序部分只有一个元素（数组的第一个元素）。算法遍历未排序部分，将每个元素插入到已排序部分的适当位置，从而使已排序部分始终保持有序。

Introsort 中插入排序的使用：

在 Introsort 中，插入排序通常用于处理小规模子数组。具体而言，当子数组的大小小于一个预定义的阈值时，Introsort 会使用插入排序来代替快速排序。这个阈值通常设置为 10 至 16 之间，具体值可以根据实际情况调整。

内省排序算法执行流程

初始化：

设置递归深度限制 depth_limit，通常为 2 * log₂(n)，其中 n 是待排序数组的长度。

快速排序：

开始时使用快速排序算法对数组进行排序。

递归地应用快速排序，直到达到某个递归深度或子数组大小条件。

深度检测与切换到堆排序：

如果递归深度达到 depth_limit，则停止使用快速排序，转而使用堆排序。

这是为了防止快速排序在最坏情况下性能退化到 O(n²)。

小数组使用插入排序：

如果子数组的大小小于某个阈值 threshold（例如 10 或 16），则使用插入排序。

插入排序对于小数组非常高效。

内省排序中的算法切换情况

初始阶段：快速排序

算法：快速排序

条件：递归开始时

描述：快速排序是内省排序的主要排序算法，它通过递归地将数组分割成较小的部分来进行排序。

当递归深度达到一定程度：堆排序

算法：堆排序

条件：递归深度达到 depth_limit

描述：一旦递归深度达到 depth_limit，内省排序将停止使用快速排序，并切换到堆排序。这是因为堆排序具有 O(n log n) 的最坏情况性能，可以避免快速排序最坏情况性能退化的问题。

当元素个数小于一定程度：插入排序

算法：插入排序

条件：子数组大小小于 threshold

描述：当子数组大小小于预定义的阈值 threshold 时，内省排序将使用插入排序。这是因为插入排序对于小数组非常高效，能够减少递归调用的开销，并且在小数组上通常比快速排序更快。

内省排序什么时候使用插入排序,什么时候使用堆排序.

当初始待排序数组元素个数小于10或16,则直接使用插入排序,而不是快速排序。这是因为插入排序对于小规模数组非常高效，而且不需要递归调用，可以减少额外的开销。
快速排序在递归过程未超过(大于等于)最大限制层数,且元素个数小于10或16,也直接使用插入排序,完成最终排序.
在上述条件都不满足的情况下(元素个数大于10或大于16的情况下),递归达到最大层次时,使用堆排序.