插入排序

插入排序是一個簡單的排序算法。這種排序算法是就地比較基礎的算法,其中一個項目被採取,其適當的位置進行搜索,而且此項目將插入到特定的位置不斷增長的排序列表。該算法是不適合大的數據集作爲它平均值和最壞情況的複雜性是O(n2) 其中n是的項目數量。

僞代碼

procedure insertionSort( A : array of items )
int holePosition
int valueToInsert

for i = 1 to length(A) inclusive do:
/* select value to be inserted */
valueToInsert = A[i]
holePosition = i
/*locate hole position for the element to be inserted */

  while holePosition > 0 and A\[i-1\] > valueToInsert do:
     A\[holePosition\] = A\[holePosition-1\]
     holePosition = holePosition -1
  end while

  /\* insert the number at hole position \*/
  A\[holePosition\] = valueToInsert

end for
end procedure

要查看C編程語言插入排序的實現,請點擊這裏