1. import java.util.Arrays;
    3. import org.junit.Test;
    5. /**
    6.  * 希尔排序
    7.  * 插入排序的一种
    8.  */
    9. public class HeerSort {
    11.     //希尔排序，它包括了交换法和移动法两种方式
    12.     public int[] heerSort(int[] arrays){
    13.         if(null == arrays){
    14.             throw new NullPointerException("arrays is null");
    15.         }
    16.         if(!(arrays.length>0)){
    17.             return arrays;
    18.         }
    19.         int[] sortArrays = Arrays.copyOf(arrays, arrays.length);
    20. //        sort(sortArrays);
    21.         sortOpt(sortArrays);
    22.         return sortArrays;
    23.     }
    25.     //移动法
    26.     private int[] sort(int[] sortArrays){
    27.         int length = sortArrays.length;
    28.         // 先求出最大区间值
    29.         int rCtl = 1;
    30.         while(rCtl*2+2<length){
    31.             rCtl = rCtl*2+2;
    32.         }
    33.         // 循环---将区间值减半
    34.         while (rCtl>0){
    35.             // 从第rCtl位开始，按区间进行插入排序
    36.             for(int i = rCtl;i<rCtl*2;i++){
    37.                 // [1,*,*,*,3,*,*,*,2,*,*,*,7,*,*,*,5,*,*,*]
    38.                 for(int j = i;j<length;j+=rCtl){
    39.                     // 找到插入的位置
    40.                     int insertnum = j;
    41.                     int temp = sortArrays[j];
    42.                     for(int c = j-rCtl;c>=0;c-=rCtl){
    43.                         // 将在j前面的值，如果大于j，就往后挪一位
    44.                        if(sortArrays[c]>temp){
    45.                             sortArrays[c+rCtl] = sortArrays[c];
    46.                             insertnum = c;
    47.                        }else{
    48.                            break;
    49.                        }
    50.                     }
    51.                     sortArrays[insertnum] = temp;
    52.                 }
    53.             }
    54.             rCtl=rCtl/2;
    55.         }
    56.         return sortArrays;
    57.     }
    59.     //代码优化写法
    60.     // 最外部不需要跨区间去循环，将外部跨区间循环与区间内部循环合成一个循环
    61.     // 因为本质还是从 0+fctl的位置一直遍历到最后一个
    62.     private void sortOpt(int[] arrays){
    63.         int len = arrays.length;
    64.         //定义区间大小
    65.         int fctl = 1;
    66.         //计算出最大区间
    67.         while(2*fctl+2<len){
    68.             fctl = 2*fctl+2;
    69.         }
    71.         while(fctl>0){
    72.             for(int i = fctl;i<len;i++){
    73.                 int sortValue = arrays[i];
    74.                 int insertKey = i;
    75.                 //找到待排序的值所在的分组中该插入的位置
    76.                 while((insertKey-fctl)>=0&&sortValue<arrays[insertKey-fctl]){
    77.                     arrays[insertKey] = arrays[insertKey-fctl];
    78.                     insertKey-=fctl;
    79.                 }
    80.                 arrays[insertKey] = sortValue;
    81.             }
    82.             fctl = fctl/2;
    83.         }
    84.     }
    86.     @Test
    87.     public void test(){
    88.         int [] arr1 = new int[]{9,3,5,7,2,8,4,1,6,2};
    89.         System.out.println(Arrays.toString(heerSort(arr1)));
    90.     }
    91. }