插入排序

插入排序是一個簡單的排序演算法。這種排序演算法是就地比較基礎的演算法，其中一個專案被採取，其適當的位置進行搜尋，而且此專案將插入到特定的位置不斷增長的排序列表。該演算法是不適合大的資料集作為它平均值和最壞情況的複雜性是O(n²) 其中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程式設計語言插入排序的實現，請點選這裡