排序算法-希尔排序（Java实现）

希尔排序

希尔排序是希尔（Donald Shell）于1959年提出的一种排序算法。希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序，同时该算法是冲破O(n2）的第一批算法之一。

基本思想

设待排序元素序列有n个元素
1.取一个整数increment（小于n）作为间隔将全部元素分为increment个子序列
2.每间隔increment取一个元素，并放在同一个子序列中，对每个子序列实行直接插入排序。
3.缩小间隔increment
4.重复上述子序列划分和排序工作。直到increment=1，即所有元素放在同一个子序列中进行最后的排序。

---

简单点~

假设有数组：{a0,a1,a2,a3,a4,a5,a6,a7,a8,a9}
此时 n = 10
1.一般情况下，我们取increment为：10/2 = 5,则此时：{a0,a5}、{a1,a6}、{a2,a7}、{a3,a8}、{a4,a9}这五组就是该数组的子序列,分别对这些子序列进行插入排序。
2.我们再取increment为：5/2 = 2，则此时：{a0,a2,a4,a6,a8}和{a1,a3,a5,a7,a9}这两组就是该数组的子序列,分别对这两个序列进行插入排序。
3.我们再取increment为：2/1 = 1,则此时：{a0,a1,a2,a3,a4,a5,a6,a7,a8,a9}所有元素都在同一个子序列中。
4.此时对其进行插入排序，因为有前面的工作基础，大多数元素已经基本有序，所以排序速度仍然很快。
从上面我们可以看到，增量increment是在逐渐减小的，所以这个方法我们也叫它为：缩小增量排序。

---

图示：

image

---

代码实现

public class ShellSort {
public static void main(String[] args) {
    int[] arr = {4,6,7,4,3,7,34,95,33,67,88,33};
    shellSort(arr);
    System.out.println(Arrays.toString(arr));
}
public static void shellSort(int[] arr) {
    int n = arr.length;
    int increment = n/2;
    for(;increment>0;increment/=2) {
        //下面这段代码和插入排序相同，只是这里的间隔是increment
        //直接插入排序的间隔是1
        int i = increment;
        for(;i<arr.length;i++) {
            int temp = arr[i];
            int t = i-increment;
            while(t >= 0 && arr[t] > temp) {
                arr[i] = arr[t];
                t -= increment;
            }
            arr[t+increment] = temp;
            
        }
    }
}

---

本篇完，如果有错误的地方欢迎大家指正
不定时发发笔记，欢迎大家来搞~
我的公众号：Java小部落