希尔排序

希尔排序 - 在插入排序的基础提高了一定的效率

核心思想:

相较于插入排序,相邻交换次数较多,希尔排序的思想是使数组中任意间隔为h的元素有序.(h有序数组) 这个h间隔就是"增量序列",并且从最大的h开始排序然后h减小一直到1,数组间隔越来越小一直到1(也就是说到间隔为1的插入排序即可保证排序),即排序完成

三层循环:

第一层循环:用来计算间隔h的值

第二层循环:从h下标开始遍历数组

第三层循环:比较array[i]和array[i-h]的大小逆序交换

伪代码实现:

 1 public static void sort(int[] array){
 2 
 3     int length = array.length;
 4     int h = length;
 5 
 6        while(h>=1){
 7               //向上取整   1.3333 = 1
 8               int h = (int)Math.ceil(h/2);
 9               for(int i=h;i<n;i++){
10 
11 
12                      for(int j=i;j>=h;j-=h){
13 
14                           if(array[j]<array[j-h]){
15            
16                                  exchange(array,j,j-h);
17 
18                           }
19                     }
20               }
21      }
22 
23 }