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

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;
        }
    }      
}

此外，这种方法的比较或交换次数 more/less 是多少？

在此先感谢您的帮助。

Answer 1

此代码是 insertion-sort 实现。看一下内部循环：

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

或简化：

for(j = 0; j < i ; j++)
    if(a[i] < a[j])
        swap(a[i], a[j]);

现在我们知道子数组a[0:i - 1]已经从外层循环的前一个运行排好序了。这是找到我们需要插入 a[i] 的索引 n 并将索引在 [n, i - 1] 范围内的所有元素推高一个索引的逻辑高尔夫球版本：

while(j < i && a[j] <= a[i])
    j++;

//insert a[i] at the appropriate index
int tmp = a[j];
a[j] = a[i];

//push all elements starting from index n one index further
for(; j < i; j++){
    int swap = tmp;
    tmp = a[j];
    a[j] = swap;
}

这两个代码片段的逻辑等价如下：
直到搜索索引 n（insertion-index 为 a[i]），不会发生交换。现在我们换掉 a[i] 和 a[n]。从那时起，a[i] 将等同于上述代码中的 tmp 变量。由于数组的其余部分仍然按索引 i - 1 排序，我们现在将每个元素与其前一个元素交换，该元素当前存储在索引 i 处。绝对是打得不错的 insertion-sort.

外循环就是标准的

for(i = 0; i < array_length; i++)
     insert a[i] at appropriate position

Answer 2

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

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

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

i 每次迭代的潜在客户元素最初是 a[i]。
您对序列的 already-sorted 部分进行线性枚举，寻找 a[i] 所属的位置
找到位置后（除非它已经在它所属的位置），将 a[i] 与当前位于目标中的元素 a[j] 交换。
从那时起，a[i] 的原始值现在在序列中是 in-place，但是...
对于排序后的序列的其余部分，swap-comparison 保证会针对存储在 a[i] 中的任何值触发为真（提示：为什么要这样做？），因为之前的值成功了，它已经排序了。因此，a[i]不断地被排序后的序列中的下一个值替换，直到它最终拥有最大值，也就是它所属的by-definition。

因此，是的，这是insertion-sort。它在每个主要迭代的 ever-expands 整体的开头维护一个排序序列。并且对于每个主要迭代，前景元素被“插入”并且尾随元素被向下移动以形成可用的孔来做到这一点。

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

相当多 需要对您的方法进行更多比较。每次迭代保证线性O(n)复杂度，有n次迭代。因此，您保证具有 O(N^2) 的比较复杂性，这是低效排序算法的祸害。不只是 worst-case；保证.

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));
}

如果您刚开始使用 C++，那可能 seems like Greek（没有冒犯希腊人的意思），但它使用了两种基本算法，使其效率惊人：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

请注意，旋转需要没有比较。

显然，此模板解决方案不是某些补救算法课程的人会提交的内容。但我希望它能给您一些关于 insertion-sort 如何通过以下方式最小化比较的想法：

对序列的 already-sorted 部分使用二分查找以尽量减少比较。
执行旋转时使用无比较。

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

Insertion sort or a variation of selection sort?

c++

algorithm

sorting

insertion-sort