java实现插入排序代码

发布时间:2020-05-29 16:07:08 作者:鸽子
来源:亿速云 阅读:237
插入排序
实现方式
  1. 直接插入排序
    • 将待排序区间的左边[0, i)看做有序区间,[i, size)看做无序区间,遍历无序区间的元素,全部插入到有序区间后,排序结束
    • 代码1(推荐):
      public void insertSort(int[] array) {
              int length = array.length;
              //遍历无序区间[1, length)
              for (int i = 1; i < length; i++) {
                      //表示当前需要被插入到有序区间的元素
                      int tmp = array[i];
                      int j;
                      //遍历有序区间[0, i)
                      //不写等于是为了保证排序的稳定性
                      for (j = i - 1; j >= 0 && array[j] > tmp; j--) {
                              array[j + 1] = array[j];
                      }
                      array[j + 1] = tmp;
              }
      }
    • 代码2(不推荐):
    • 在遍历有序区间找对应位置时,由于每次比较都可能进行次交换,时间和空间上会造成一定程度的浪费,因此效率不如代码1
      public void insertSort2(int[] array) {
              int length = array.length;
              //遍历无序区间[1, length)
              for (int i = 1; i < length; i++) {
                      //遍历有序区间
                      for(int j = i; j >0; j--) {
                              //如果待排序元素小于有序区间的最后一个元素就与其交换
                              if(array[j] < array[j - 1]) {
                                      int tmp = array[j];
                                      array[j] = array[j - 1];
                                      array[j - 1] = tmp;
                              }
                      }
              }
      }
  2. 折半插入排序

    • 同样是将待排序区间分为了有序和无序两个区间,但是在遍历插入位置时采用了二分查找的方式
    • 找到要插入的位置后将有序区间中该位置后的的元素向后搬移一位
    • 然后将要插入的元素插入
    • 代码:

      public void bsInsertSort(int[] array) {
              for(int i = 1; i < array.length; i++) {
                      int tmp = array[i];
                      int left = 0;
                      int right = i;
      
                      //在有序区间内进行二分查找操作,找到要插入的位置
                      while(left < right) {
                              int mid = (right + left) >>> 1;
                              if(array[mid] <= tmp) {
                                      left = mid + 1;
                              } else {
                                      right = mid;
                              }
                      }
      
                      //将有序区间内[left, i)中的元素向后移动一位
                      for(int j = i - 1; j >= left; j--) {
                              array[j + 1] = array[j];
                      }
                      array[left] = tmp;
              }
      }
性能分析

推荐阅读:
  1. 插入排序
  2. java实现选择排序完整代码

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

java 插入排序 ava

上一篇:​springboot中集成shiro框架的方法

下一篇:Kubernetes中YAML的语法格式和使用方法

相关阅读

您好,登录后才能下订单哦!

密码登录
登录注册
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》