插入排序
插入排序
镜子哥哥 发表于1年前
插入排序
  • 发表于 1年前
  • 阅读 4
  • 收藏 0
  • 点赞 0
  • 评论 0

腾讯云 新注册用户 域名抢购1元起>>>   

摘要: 自己写的时候一直在移动后交换,错了

原理

插入排序外循环标记未排序部分最左端的数据,内循环从该位置左侧开始向左移动,直到找到合适该数据插入的位置。

如下图所示,每次选择一个元素K插入到之前已排好序的部分A[1…i]中,插入过程中K依次由后向前与A[1…i]中的元素进行比较。若发现发现A[x]>=K,则将K插入到A[x]的后面,插入前需要移动元素。 插入排序原理

不变性

(算法运行时保持不变的条件):它总是局部有序的。

效率

比较 平均 N(N-1)/4 次; 复制 N(N-1)/4 次 ;

总时间级 O(N2)

复制与交换速度不同,所以对于随机数据,比冒泡快一倍,比选择略快。

实现代码

//这是错的,有不必要的复制
public void insert(int[] array) {
   int len = array.length;
   for (int a = 1; a < len; a++) {
       int temp = array[a];
       for (int b = a - 1; b >= 0; b--) {
           if (array[b + 1] < array[b]) {
               array[b + 1] = array[b];
               array[b] = temp;
               }
           }
       }
   }

下面才是真正的

public void insert(int[] array) {
        int len = array.length;
        for (int a = 1; a < len; a++) {
            int temp = array[a];
            int b = a - 1;
            for (; b >= 0 && temp < array[b]; b--) {
                array[b + 1] = array[b];
            }
            array[b + 1] = temp;
        }
    }
标签: 插入排序
共有 人打赏支持
粉丝 2
博文 19
码字总数 14425
×
镜子哥哥
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: