插入排序

插入排序是一个简单的排序算法。这种排序算法是就地比较基础的算法，其中一个项目被采取，其适当的位置进行搜索，而且此项目将插入到特定的位置不断增长的排序列表。该算法是不适合大的数据集作为它平均值和最坏情况的复杂性是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编程语言插入排序的实现，请点击这里