排序算法-希尔排序

希尔排序

希尔排序(Shell's Sort)是插入排序的一种又称“缩小增量排序”（Diminishing Increment Sort），是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因 D.L.Shell 于 1959 年提出而得名。希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至 1 时，整个文件恰被分成一组，算法便终止。

思路

• 对一组数据进行分组排序，以此对数据进行一定的“粗略调整”。
• 开始可以将数据分为两两一组，一组元素之间的间隔是数组长度的一半，这个间隔我们称为跨度。
• 分好组的元素进行比较、排序后，继续缩减跨度、分组排序。直到跨度为1时，让每个元素独立排序，排序方式用直接插入法即可。
  

  import java.util.Arrays;
  public class ShellSort{
    public static void sort(int[] arr){
        //希尔排序的增量
        int d = arr.length;
        while(d > 1){
            //使用希尔增量的方式，即每次折半
            d = d / 2;
            for(int x = 0; x < d; x++){
                for(int i = x + d; i < arr.length; i = i + d){
                    int temp = arr[i];
                    int j;
                    for (j = i-d; j>=0 && arr[j]>temp; j = j-d) {
                        arr[j+d] = arr[j];
                    }
                    arr[j+d]=temp;
                }
            }
        }
    }
    public static void main(String[] args) {
        int[] arr = {5,9,6,0,1,2,3,8};
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }
  }