[算法學習筆記]直接插入排序筆記

直接插入排序概念:

帶排元素放在elem[0...n-1]中，初始化時，elem[0]自成1個有序區，無序區為elem[1...n-1]，從i=1起，到i=n-1，依次将elem[i]插入有序區[0...n-1]中

直接插入排序算法步驟:

1.在目前有序區域R[1,i-1]中查找R[i]的正确插入位置K(1<=K<=i-1)

2.将R[K,i-1]中的記錄均向後移動

3.移動後騰出K位置，插入R[i]

(最壞)時間複雜度:O(n^2)

空間複雜度:O(1)