Java实现希尔排序 及其 详解

希尔排序

概述

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

插入排序的速度虽然比冒泡和选择快，但是还是比较慢且有缺陷的。因为如果一个最小的数字在数组最后面，则对它进行排序的时候，要循环很多次，将其插入到数组的最前端，而希尔排序则解决了这个问题。它与插入排序类似，只是把一组插入排序，改为了多组。一开始是每隔length/2个数字为一组进行插入，则第一轮插入的时候，比较小的数字都插入到了数组的前段，相对于插入排序，少了许多次循环的过程。

它把一组数组，改为了多组，分别进行插入排序。分隔这些不同组插入排序的东西，我管它叫做“步长”。步长一开始是 length/2 ,随后不断 / 2。

原理

图源：尚硅谷java数据结构视频

以上图举例：

数组长度为10，则初始步长为5，即将此数组分为5组，每隔5个下标 (一个步长) 的数字为一组，分别进行插入排序。

第一次排序完成后，步长继续 /2，为2，即将数组分为2组，每隔两个下标的数字为一组。分别对这两组进行插入排序。

第一次排序完成后，步长继续 /2，为1，即数组不分组，直接进行插入排序。

代码实现

package sort;

public class ShellSort {
          
   

    public static void main(String[] args) {
          
   
//        int[] array = {1,5,4,8,7,6,2,3,9};
//        int[] ints = shellSort(array);
//        for (int anInt : ints) {
          
   
//            System.out.print(anInt);
//        }
        int[] array = new int[80000];
        for (int i = 0; i < array.length; i++) {
          
   
            array[i] = (int)(Math.random()*800000);
        }
        long startTime=System.currentTimeMillis();
        shellSort(array);
        long endTime=System.currentTimeMillis();
        System.out.println("程序运行时间： "+(endTime - startTime)+"ms");
        //希尔排序排序80k长度的数组，在我这台电脑上只用了不到0.1秒，而插入排序则需要2秒多
    }
    public static int[] shellSort(int[] array){
          
   
        //控制步长，每循环一次就除二
        for (int n = array.length/2; n > 0; n /= 2 ){
          
   
            //从下标为步长的元素开始，依次向后循环
            //不用担心前面的元素，因为下面j层的循环，会依次和前面的数字进行比较。
            for (int i = n; i < array.length; i++) {
          
   
                // 从下标为[步长]的数字开始，向前 隔一个步长 进行比较
                // 如果后一个比前一个小，则交换，如果不是，则返回上一层循环，
                // i+1后再进行【如果后一个比前一个小，则交换】的比较
                // 之后j-n，再和一开始位置的两个步长距离的数字进行比较
                // 如此反复
                for (int j = i; j > 0 && j-n >= 0 && array[j] < array[j-n]; j-=n) {
          
   
                    int temp = array[j];
                    array[j] = array[j-n];
                    array[j-n] = temp;
                }
            }
        }
        return array;
    }
}