首页 > 其他 > 详细

【算法-排序之三】插入排序

时间:2014-03-14 15:39:31      阅读:323      评论:0      收藏:0      [点我收藏+]

算法-排序之插入排序

         插入排序是一种简单的排序算法,这是一种从小范围到大范围的递归思想,这种思想类似于数学推导中的递归,首先在最小规模n(1个数的队列)满足要求,再考虑n+1时需要的操作,递归直到最终的结果。当问题规模很大无从下手时,在问题最小规模点思考,然后逐渐递加,不失为一个很好的选择。
         1.插入排序InsertSort
         核心:以一个人为初始序列,从第二个人开始每次将一个人插入该队列中
         明白了插入排序的核心,你能轻易理解插入排序的步骤:
         1.将第一个数作为起始序列
         2.将下一个数插入序列,
         3.直到所有数全部插入序列,得到完整有序结果
                                       bubuko.com,布布扣
                                                                      以3为起始序列,分成如下
                              bubuko.com,布布扣
                                                                  将9插入左边的序列
                             bubuko.com,布布扣
                                                                   将5插入左边的序列
                           bubuko.com,布布扣
            左边的有序序列会慢慢将右边的序列全部包含,最后左边的序列便是我们需要最终有序结果。需要注意的是,在插入数时,需要根据插入数的大小找到相应的插入位置。
              bubuko.com,布布扣
              下面是可复制代码:
           2.时间复杂度
            O(n*2),插入排序的时间复杂度分析较为复杂,有兴趣可以探究一下。
           3.空间复杂度
           一个额外交换空间,O(1)。

【算法-排序之三】插入排序,布布扣,bubuko.com

【算法-排序之三】插入排序

原文:http://blog.csdn.net/lovecodeless/article/details/21231257

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!