插入排序和選擇排序的區別

插入排序

• 在插入排序中，值被插入到列表/陣列中，其中一些值是先前排序的。

• 它是一種穩定的排序演算法。

• 最佳情況時間複雜度為 O(N)（當列表已按升序排序時）。

• 定義一個鍵值，並從頭到尾迭代陣列。

• 迭代期間的當前元素與鍵值進行比較。

• 插入排序期間進行的比較操作次數少於執行的元素交換次數。

• 如果鍵元素小於與其比較的元素，則將其與之前的元素進行比較。

• 大於鍵的元素向上移動一個位置，為要交換的元素騰出空間。

• 元素是預先知道的，只有它們的位置在插入排序期間確定。

選擇排序

• 在選擇排序中，首先從列表中獲取最小或最大數。

• 列表按升序或降序排序。

• 它被認為是一種不穩定的排序演算法。

• 在所有情況下，時間複雜度都是 O(n 平方)。

• 與插入排序相比，效率較低。

• 迭代期間進行的比較次數多於執行的元素交換次數。

• 列表中每個元素的位置是預先知道的。

• 這意味著使用者只需搜尋需要插入到特定位置的元素。

AmitDiwan

更新於: 2021年3月23日

2K+ 閱讀量

開啟你的 職業生涯

透過完成課程獲得認證

立即開始