运行时间插入排序(Running Time For Insertion Sort)

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次。上）

我不知道以后做找到插入排序的运行时间是什么？如果你可以纠正我的工作。谢谢。

Answer 1:

下面是两行通用的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)这意味着当前元素交换到插入点。这种旋转是在迄今已分类的元素数呈线性关系。既然是嵌套在主循环中，插入排序的整体复杂性是二次，ie.e. O(N^2) 您的代码集成交换和搜索插入点，但不改变的复杂性。

请注意，当输入电压范围已经排序，插入点永远是等于元素指向it ，这意味着该std::rotate不必在所有交换任何东西。足够聪明，优化编译器应该能够执行优化。如果是这样的情况下，在一个有序区间插入排序具有线性复杂性。

类似的2线的方法来选择排序给出这里。