插入排序的运行时间 [英] 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;
}

我很难弄清楚插入排序的最坏情况. 因此，给定的数组按降序排列，我们要按升序对其进行排序.

I'm having trouble figuring out the worse case for Insertion sort. So, the array given is in descending order, and we want to sort it in ascending order.

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

The outer loop goes through the array. So, it runs (n times). O(n) int tmp=a[p] ---- This statement gets executed n times. O(n) The inner loop get executed (1+2+3+4+5+6+.... +n-1) times. O(n^2) a[j]= tmp-------- This statement get executed n times. O(n)

我不确定找到插入排序的运行时间后该怎么办? 如果可以，请更正我的工作. 谢谢.

I'm not sure what to do after to find the running time for Insertion sort? Correct my work if you can. Thank you.

推荐答案

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

Here's a two-line generic C++11 implementation of insertion sort

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<).

The algorithm takes a range of elements (given by the two iterators first and last) and a comparison function (which is defaulted to the possibly builtin operator< for the elements pointed to).

主循环(元素数量呈线性)使子间隔[first, it)保持排序，并重复搜索下一个元素放置位置的插入点.它等效于您的主循环.使用 二进制搜索 (对数复杂).在您的代码中，您使用反向线性搜索(具有线性复杂度，但可能会有更好的缓存行为).

The main loop (linear in the number of elements) keeps the subinterval [first, it) sorted, and repeatedly searches for an insertion point of where to put the next element. It's equivalent to your main loop. It does so with a binary search (logarithmic complexity). In your code you use a reverse linear search (wich has linear complexity but possibly better caching behavior).

找到插入点后，只需 旋转 两个范围[insertion, it)和[it, it+1)，这意味着将当前元素交换到插入点.到目前为止，该旋转是线性的，已排序的元素数量是线性的.由于它嵌套在主循环中，因此插入排序的总体复杂度是二次的，即O(N^2).您的代码将交换和搜索插入点集成在一起，但这并不会改变复杂性.

After it has found the insertion point, it simply rotates the two ranges [insertion, it) and [it, it+1), which means swapping the current element into the insertion point. This rotation is linear in the number of elements that has been sorted so far. Since it is nested in the main loop, the overall complexity of insertion sort is quadratic, ie.e. O(N^2). Your code integrates the swapping and searching for an insertion point, but that does not change the complexity.

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

Note that when the input range is already sorted, the insertion point will always be equal to the element pointed to by it, and this means that the std::rotate does not have to swap anything at all. A sufficiently smart and optimizing compiler should be able to perform that optimization. If that is the case, insertion sort on a sorted range has linear complexity.

在此处提供了类似的两行选择排序方法.

A similar 2-line approach to selection sort is given here.

这篇关于插入排序的运行时间的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！