插入排序

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