希尔排序算法

什么是希尔排序

希尔排序是缩小增量排序，希尔排序是采用自定义增量的步长的方式来进行比较交换。而步长从开始递减至1，实际就是以递减步长的方式，将排序范围逐渐减小到1，就是相邻的元素之间了。

希尔排序的特点

希尔排序算法与步长有直接关系。步长依次递减，数组的局部越来越有序了。

希尔排序算法思想

因为希尔排序是通过比较相距一定间隔的元素来工作的。所以先要自定义步长的范围。然后选择一个当前元素，依次按照步长来寻找指定步长的元素进行比较，比较选择出最小的元素，如果比当前元素小于指定步长的元素，就进行交换，相反就退出当前的循环查找比较。

希尔排序的实现

     public static void shellSort(int[] arr) {
        if (arr.length == 0) {
            return;
        }
        
        int step = arr.length / 2;
        
        while(step > 0) {
            for (int i = step ; i < arr.length ; i++) {
                int temp = arr[i];
                int j = i;
                while (j >= step) {
                    if (temp < arr[j - step]) {
                        arr[j] = arr[j - step];
                    } else {
                        break;
                    }
                    j -= step;
                }
                arr[j] = temp;
            }
            step /= 2;
        }
        
    }

测试：

    public static void main(String[] args) {
        int[] arr1 ={35, 17, 11, 28, 12, 41, 75, 15, 96, 58, 81, 94, 95};
        shellSort(arr1);
        printArr(arr1);
    }

结果：

12.jpg