首页 > 编程语言 > 详细

直接插入排序

时间:2015-08-28 02:20:14      阅读:241      评论:0      收藏:0      [点我收藏+]

一、原理

        每次从无序数据中取出一个,插入到有序的数据列表中合适的位置,保证插入后的列表依然后续。

       如:一堆牌,原先手上没有牌,依次从牌堆上取一张到手上,第一张牌到手上时,手上只有一张牌,即为有序,取第二张和第一张比较,插入合适的位置,保证手上的牌依然后续,依次类推。

二、时间和空间复杂度

      最坏的情况是数据是倒序的,时间复杂度为: T(n)=O(1+2+....+n-1)=O((n^2)/2 - n/2)=O(n^2)

      最好的情况是数据已经是有序的,时间复杂度为:O(n)

      空间复杂度:O(1)

三、排序过程图

    技术分享


四、代码实现

void insert_sort(int arr[], int arr_size)
{
     int index_tra; //用于外层循环,遍历整个数组
     int index_sort; //用于内层循环,找到合适的位置
     int tmp; //
                
     index_tra = 1;
     while (index_tra < arr_size) {
         index_sort = index_tra - 1;
         tmp = arr[index_tra];
         while (index_sort >= 0 && arr[index_sort] > tmp) {
              arr[index_sort + 1] = arr[index_sort];
              index_sort--;
           }
          arr[index_sort + 1] = tmp; //找到合适的位置,插入
          index_tra++;
     }    
 }

直接插入排序

原文:http://happytree007.blog.51cto.com/6335296/1689098

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