1 
for (int p=1; p < a.size(); p++) {
    int tmp = a[p];
    for(j=p; j>0 && tmp < a[j-1]; j--) {
        a[j] = a[j-1];
    }
    a[j] = tmp;
}

我无法找出插入排序的最坏情况。因此，给定的数组是按降序排列的，我们要按升序对其进行排序。

外循环通过数组。因此，它运行（n 次）。O(n) int tmp=a[p]---- 该语句被执行 n 次。O(n) 内部循环被执行 (1+2+3+4+5+6+.... +n-1) 次。O(n^2) a[j]= tmp-------- 该语句被执行 n 次。上）

我不确定在找到插入排序的运行时间后该怎么做？如果可以，请纠正我的工作。谢谢你。

4

2 回答 2

2

这是插入排序的两行通用 C++11 实现

template< typename ForwardIterator, typename Compare = std::less<typename std::iterator_traits<ForwardIterator>::value_type> >
void insertion_sort(ForwardIterator first, ForwardIterator last, Compare cmp = Compare())
{
        for (auto it = first; it != last; ++it) {
                auto const insertion = std::upper_bound(first, it, *it, cmp);
                std::rotate(insertion, it, std::next(it));
        }
}

该算法采用一系列元素（由两个迭代器first和给出last）和一个比较函数（默认为operator<指向元素的可能内置函数）。

主循环（元素数量呈线性关系）保持子区间的[first, it)排序，并反复搜索放置下一个元素的插入点。它相当于你的主循环。它通过二进制搜索（对数复杂度）来实现。在您的代码中，您使用反向线性搜索（具有线性复杂性但可能有更好的缓存行为）。

找到插入点后，它只是旋转两个范围[insertion, it)和[it, it+1)，这意味着将当前元素交换到插入点。这种旋转与迄今为止已排序的元素数量呈线性关系。由于嵌套在主循环中，所以插入排序的整体复杂度是二次的，即 O(N^2). 您的代码集成了插入点的交换和搜索，但这不会改变复杂性。

请注意，当输入范围已经排序时，插入点将始终等于 指向的元素it，这意味着std::rotate根本不需要交换任何东西。足够智能和优化的编译器应该能够执行该优化。如果是这种情况，则排序范围上的插入排序具有线性复杂性。

这里给出了一个类似的 2 行选择排序方法。

于 2013-01-29T08:27:27.857 回答
1

外循环执行 n 次。

内部循环的每次运行都会执行 0 到 p-1 次，其中 p 从 0 到 n 变化。在最坏的情况下，它将执行 p-1 次。如果 p 从 0 变化到 n，则平均而言，p 为 n/2。因此，内循环的最坏情况复杂度是 O(p-1) = O(n/2-1) = O(n)。

除了循环之外，代码都是 O(1)（最重要的是，内部循环内的代码是），所以只有循环才是重要的。

O(n) * O(n) = O(n^2)。

QED。

大致就是你自己给的分析。

于 2013-01-29T09:00:47.607 回答