排序算法之希尔排序

2021-07-14 22:05

阅读：525

标签：描述 ram 数据结构大量性能分析分析分享图片 logs 作者

来源

　　希尔排序是插入排序的改进版，插入排序是要和每一个元素进行比较，如果本身就有序，这个比较就显得多余，那么我们可以设定一个间隔来解决，这个就叫做希尔排序。希尔排序是早一批突破O(n^2)的排序算法

过程

　　图来自https://www.cnblogs.com/chengxiao/p/6104371.html，感谢作者写这么详细

　　上面的图就是希尔排序的基本逻辑，那么这个间隔我们该怎么选择呢，上网查大家一般都分为两种

　　　　第一种：取得数组的长len，每一次都用len/2来缩短步长

　　　　第二种：h=3*h+1；用这个公式来计算步长（1,4,13,40...），什么时候结束？h>=en/3的时候结束

　　最开始我就是在这里绕了好久，后来才发现这个间隔的取法很多人不相同所以代码判断临界点就不一样

 1 //希尔排序
 2     public void shellSort(int[] nums){
 3         
 4         int len = nums.length;
 5         int gap = 0;
 6         //生成gap
 7         while(gap ){
 8              gap = gap * 3 + 1;
 9         }
10         while(gap >= 1){
11             for(int i=gap; i){
12                 //找到与自己增量匹配元素的位置
13                 int j = i - gap;
14                 //将小一点的放前面
15                 while(j>=0 && nums[j]>nums[i]){
16                     //交换
17                     int temp = nums[j];
18                     nums[j] = nums[i];
19                     nums[i] = temp;
20                 }
21             }
22             //逐步缩短步长
23             gap = (gap - 1) / 3;
24         }
25     }