数据结构----排序--插入法排序

原创 lronelove 随笔 浅谈数据结构 67阅读 2018-11-14 17:56:29 举报

插入法排序

1.插入法排序思路:

  • 假设有一个数组 arr = [5, 4, 6, 1, 3, 2]
  • 初始化的时候有一个已经排序好的数组sortedArr = [arr[0]],里面只有一个值,即arr[0]。只有一个元素的数组肯定是排好序的
  • 循环遍历arr,从下标1开始(因为arr[0]已经在排序好的数组里面)。
  • 用一个值j存储即将插入值的下标;如果要插入的值比sortedArr里面的任何元素都要小,那么插入到最前面。
  • 当即将插入的元素比sortedArr[j]大的时候,j++, 插入的位置往后移,直到移动到遇见一个比它大的元素,或者最后一个。

2.插入法排序代码如下:

3.插入法需要两层循环,复杂度O(n^2), 后面应该会出点其它的排序,比如分治法排序等

评论 ( 0 )
最新评论
暂无评论

赶紧努力消灭 0 回复