区块链技术博客
www.b2bchain.cn

【jdk8源码】Arrays.sort插入排序,居然还可以成对插入的讲解

这篇文章主要介绍了【jdk8源码】Arrays.sort插入排序,居然还可以成对插入的讲解,通过具体代码讲解8418并且分析了【jdk8源码】Arrays.sort插入排序,居然还可以成对插入的讲解的详细步骤与相关技巧,需要的朋友可以参考下

本文实例讲述了【jdk8源码】Arrays.sort插入排序,居然还可以成对插入的讲解。分享给大家供大家参考文章查询地址https://www.b2bchain.cn/?p=8418。具体如下:

      在jdk1.8源码中,Arrays.sort方法中运用了传统插入排序与成对插入排序,这里主要讲解这两种算法思想

源码引入

int[] b ={1,3}; Arrays.sort(a); 

Arrays

public static void sort(int[] a) {         DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);     } 

DualPivotQuicksort

    static void sort(int[] a, int left, int right,                      int[] work, int workBase, int workLen) {         // 数组长度小于286,就用快速排序         if (right - left < QUICKSORT_THRESHOLD) {         	//这里用到的就是快排             sort(a, left, right, true);             return;         }         //下边是判断数组结构,是使用快速排序还是归并排序,暂略-后期再说     } 

传统插入排序

      我们直接从这里进去看快排代码,整个代码比较长,我们今天先只看第一部分——插入排序

         if (length < INSERTION_SORT_THRESHOLD) {             if (leftmost) {                 // 传统的插入排序,从左到右排序                 for (int i = left, j = i; i < right; j = ++i) {                 	//需要插入的数ai                     int ai = a[i + 1];                     //循环查找ai的位置                     while (ai < a[j]) {                     	//如果ai小与a[j],往后移动a[j]                         a[j + 1] = a[j];                         if (j-- == left) {                         	// 遍历到最左端结束                             break;                         }                     }                     // 得到ai的位置,插入                     a[j + 1] = ai;                 }             } else {                 // 此处是成对插入排序,略             }          } 

成对插入排序

      如果数组长度小于47,就用插入排序,根据参数leftmost来选择使用传统的插入排序还是成对插入排序

      具体执行过程:上面的do-while循环已经排好的最前面的数据
      (1)将要插入的数据,第一个值赋值a1,第二个值赋值a2,
      (2)然后判断a1与a2的大小,使a1要大于a2
      (3)接下来,首先是插入大的数值a1,将a1与k之前的数字一一比较,直到数值小于a1为止,把a1插入到合适的位置,注意:这里的相隔距离为2,因为要预留出a2的位置
      (4)接下来,插入小的数值a2,将a2与此时k之前的数字一一比较,直到数值小于a2为止,将a2插入到合适的位置,注意:这里的相隔距离为1
      (5)最后把最后一个没有遍历到的数据插入到合适位置

            else {                 // 跳过最长的升序序列,这里的最长指从最左边开始的升序序列                 do {                     if (left >= right) {                         return;                     }                 } while (a[++left] >= a[left - 1]);                  // 开始遍历                 for (int k = left; ++left <= right; k = ++left) {                     int a1 = a[k], a2 = a[left]; 					// 保证a1大于a2                     if (a1 < a2) {                         a2 = a1; a1 = a[left];                     }                     // 找到a1的位置                     while (a1 < a[--k]) {                         a[k + 2] = a[k];                     }                     // 插入a1                     a[++k + 1] = a1; 					// 找到a2的位置                     while (a2 < a[--k]) {                         a[k + 1] = a[k];                     }                     // 插入a2                     a[k + 1] = a2;                 }                 int last = a[right]; 				// 最后循环找到最后一个数 				// 这里两两插入,如果是奇数,最后会剩一个,单独处理                 while (last < a[--right]) {                     a[right + 1] = a[right];                 }                 a[right + 1] = last;             }             return; 

总结:

      至此,我们学习完了传统插入排序和成对插入排序,可以看出成对插入排序的每次先插入较大的数,这样我们就可以确定另一个数肯定在插入位置的左侧,这种处理方式有点像TimSort排序中合并相邻部分的处理,先找到左边最大数在右边的位置,再找到右边最小数在左边的位置,然后只需合并这重合的部分就行了。因此它比传统的插入排序实现更快。
      由于成对插入排序在循环寻找a1,a2位置的时候,没有对左边界做判断,因此这次要注意下标越界的问题。这次省去判断,对性能的提升也是有帮助的。

本文地址https://www.b2bchain.cn/?p=8418

赞(0) 打赏
部分文章转自网络,侵权联系删除b2bchain区块链学习技术社区 » 【jdk8源码】Arrays.sort插入排序,居然还可以成对插入的讲解
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

b2b链

联系我们联系我们