java实现插入排序代码-创新互联

• 排序是将一串数据按照其某个或者某些关键字的大小进行递增或递减排列的操作我，通常指的排序是升序，排序方式是原地排序
• 下面介绍下插入排序

插入排序

• 原理：插入排序是将待排序区间分成两个区间，分别是无序区间和有序区间，遍历无序区间中的每一个元素，将其插入到有序区间的对应位置。当无序区间的元素遍历完毕后，待排序区间就有序了
• 插入排序是一个稳定的排序

实现方式

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;
          }
     }

性能分析

• 时间复杂度：
  • 最好的情况：待排序有序时，时间复杂度为O(N)
  • 最坏的情况：待排序逆序时，时间复杂度为O(N^2)
  • 平均情况：时间复杂度 为O(N^2)
• 空间复杂度：O(1)
• 稳定性：稳定
• 初始数据越接近有序，时间效率越高

另外有需要云服务器可以了解下创新互联scvps.cn，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。