c++ - 插入排序还是选择排序的变体？

Question

我有一个代码片段 here .测试了几个案例，似乎工作正常。

学习了算法后，我一下子写出了插入排序的代码，但是有疑问，这真的是传统的插入排序吗？

我觉得这可能是选择排序的变体(调整版)，这是我困惑的原因。

具体来说，这是值得关注的领域:(给定 n 元素的数组 a)

for(i=1;i<n;i++){
    for(j=0;j<i;j++){
        if(a[i] < a[j]){
            temp = a[i];
            a[i] = a[j];
            a[j] = temp;
        }
    }      
} 

此外，这种方法的比较或交换次数是多了还是少了？

在此先感谢您的帮助。

Answer 1

你的问题最直接的答案是是，就是插入排序。这是一种非常低效的插入排序，但它仍然是插入排序。

您的代码缺少决定性的步骤，即一旦确定元素的位置，就可以停止比较，然后对已排序的序列进行移位操作，从而为新元素打洞。相反，您依靠比较循环为您执行该转换，即使不再需要比较时也是如此，这不是很有效。

这可能看起来有点令人困惑，所以我将针对您的代码进行详细说明。

• i 每次迭代的前景元素最初是 a[i]。
• 您对序列中已排序的部分进行线性枚举，寻找 a[i] 所属的位置
• 一旦找到位置(除非它已经在它所属的位置)，您将 a[i] 与当前位于您的位置的元素 a[j] 交换目标。
• 从那时起，a[i] 的原始值现在就位在序列中，但是...
• 对于排序序列的其余部分，交换比较保证触发为真(提示:为什么要这样做？)针对存储在 a[i] 中的任何值，因为值之前成功的它已经被排序了。因此，a[i] 不断被排序序列中的下一个值替换，直到它最终拥有最大值，这是它所属的定义。

因此，是的，这就是插入排序。它在整体的开始处维护一个排序序列，该序列随着每次主要迭代而不断扩展。对于每个主要迭代，前景元素都被“插入”，尾随元素被向下移动以形成可用的孔来执行此操作。

... are the number of comparisons or swaps more/less with this kinda approach?

相当多您的方法需要更多的比较。每次迭代都保证线性 O(n) 复杂度，并且有 n 次迭代。因此，保证您的比较具有O(N^2) 复杂性，这是低效排序算法的祸害。不仅仅是最坏的情况； 保证。

---

C++ 插入排序

也就是说，考虑一下

template<typename Iter>
void insertion_sort(Iter first, Iter last)
{
    for (Iter it = first; it != last; ++it)
        std::rotate(std::upper_bound(first, it, *it), it, std::next(it));
}

那可能是seems like Greek (没有冒犯希腊人的意思)如果你刚开始使用 C++，但它利用了两种基本算法，使其效率惊人:std::upper_bound 和 std::rotate .

std::upper_bound对排序序列进行操作。利用这一点，它可以利用二进制搜索 算法来定位排序序列中严格大于预期值 (*it) 的第一个元素。因此，为单个前景搜索插入点的时间为 O(logN)，远优于 O(n) 的线性搜索。

一旦插入点已知，std::rotate用于通过使用插入点的迭代器将元素放置到位。它有效地做到了这一点:

0 1 2 3 5 6 4
        ^ ^ *  these will be rotated right one element

0 1 2 3 5 6 
            4

0 1 2 3   5 6 
        4

0 1 2 3 4 5 6 

请注意，旋转需要不比较。

显然，此模板解决方案不是某些补救算法类(class)的人会提交的内容。但我希望它能给你一些关于插入排序如何通过以下方式最小化比较的想法:

• 对序列的已排序部分使用二分查找，以尽量减少比较。
• 执行旋转时不使用比较。