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 次)。在)
int tmp=a[p] ---- 这个语句被执行了 n 次。在)
内部循环执行 (1+2+3+4+5+6+.... +n-1) 次。 O(n^2)
a[j]= tmp-------- 这个语句被执行了 n 次。 O(n)
我不确定在找到插入排序的运行时间之后要做什么？ 如果可以的话，纠正我的工作。 谢谢。
最佳答案
这是插入排序的两行通用 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)排序，并反复搜索放置下一个元素的插入点。它相当于你的主循环。它使用 binary search 来实现(对数复杂度)。在您的代码中，您使用反向线性搜索(具有线性复杂性但可能具有更好的缓存行为)。
找到插入点后，它简单地rotates两个范围 [insertion, it)和 [it, it+1) ，这意味着将当前元素交换到插入点。这种旋转与到目前为止已排序的元素数量成线性关系。由于它嵌套在主循环中，因此插入排序的整体复杂度是二次的，即O(N^2) .您的代码集成了插入点的交换和搜索，但这并没有改变复杂性。
请注意，当输入范围已排序时，插入点将始终等于 it 指向的元素。 ，这意味着 std::rotate根本不需要交换任何东西。足够智能和优化的编译器应该能够执行该优化。如果是这种情况，则对已排序范围的插入排序具有线性复杂度。
给出了类似的 2 行选择排序方法 here .
关于c++ - 插入排序的运行时间，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/14493978/