关注码农话题
做一个实实在在的内行人

插入排序

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

入职你的梦想 VS 变现你的技术

IT面试宝典码农市场