運行時間插入排序

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次。 O（n）

我不知道在找到插入排序的運行時間後該怎麼辦？如果可以，請糾正我的工作。謝謝。

來源

2013-01-24 Jonathan Lam

最差情況下的運行時間爲O（n^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)的排序，並重復搜索插入點放置下一個元素的位置。這相當於你的主循環。它是這樣做的，具有binary search（對數複雜度）。在你的代碼中，你使用反向線性搜索（有線性複雜性但可能更好的緩存行爲）。

找到插入點後，它簡單地rotates兩個範圍[insertion, it)和[it, it+1)，這意味着將當前元素交換到插入點。這種旋轉在迄今爲止已排序的元素的數量上是線性的。由於它嵌套在主循環中，插入排序的整體複雜度是二次的，即e。 O(N^2)。您的代碼集成了交換和搜索插入點，但這並沒有改變複雜性。

請注意，當輸入範圍已經排序時，插入點將始終等於it指向的元素，這意味着std::rotate不必交換任何東西。一個足夠聰明和優化的編譯器應該能夠執行該優化。如果是這種情況，排序範圍上的插入排序具有線性複雜度。

給出了類似的選擇排序的兩行方法here。

來源

2013-01-29 08:27:27 TemplateRex

外循環執行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-29 09:00:47

運行時間插入排序

回答

相關問題