java希尔排序

什么是希尔排序，可以参考这篇文章：希尔排序原理，图文并茂，通俗易懂

public class ShellSort {
    public static void main(String[] args) {
        int[] a = {1, 3, 5, 2, 4};
        int length = a.length / 2;

        while (length >= 1) {
            sort(a, length);
            length /= 2;
        }
        sort(a, length);

        System.out.println(Arrays.toString(a));
    }

    /**
     * @param a 排序的数组
     * @param n 步长
     * */
    private static void sort(int[] a, int n) {
        for (int i = 0; i < a.length; i++) {
            for (int j = i + n; j <a.length; j++) {
                if (a[i] > a[j]) {
                    int temp = a[i];
                    a[i] = a[j];
                    a[j] = temp;
                }
            }
        }
    }
}

发现自己写了个错的希尔排序。。。

if (a[i] > a[j]) {
  int temp = a[i];
  a[i] = a[j];
  a[j] = temp;
}

这里一不小心用了冒泡排序！！！应该是插入排序，两个元素交换位置非要使用插入排序，真让人头大。最终正确版本的希尔排序 ：

public class ShellSort {
   public static void main(String[] args) {
       int[] a = {1, 3, 5, 2, 4};
       int length = a.length / 2;

       while (length >= 1) {
           sort(a, length);
           length /= 2;
       }
       sort(a, length);

       System.out.println(Arrays.toString(a));
   }

   /**
    * @param a 排序的数组
    * @param n 步长
    * */
   private static void sort(int[] a, int n) {
       int j;
       for (int i = n; i < a.length; i++) {
           int temp = a[i];
           for (j = i - n; j >= 0; j -= n) {
               if (a[j] > temp) {
                   a[j + n] = a[j];
               } else {
                   break;
               }
           }
        
           a[j + n] = temp;
       }
   }
}         

插入排序：有序队列中右移插入元素，并且是从右向左遍历