排序算法——希尔排序

基本排序思想

算法先将要排序的一组数组按某个增量d分成若干组，每组中记录的下标相差d。对每组中全部元素进行排序，然后再用一个比较小的增量对他进行分组，在每组中再进行排序。当增量减到1时，整个要排序的数被分成了一组，排序完成。

例如：

假设待排序数组为：[49,38,65,97,76,13,27,49,55,04]

增量序列的取值一次为

5，2，1

在排序过程中，由于希尔算法需要多次排序，所以该算法排序是不稳定的

代码实现：

package com.company;
import java.util.Arrays;
public class Main {

    public static void main(String[] args) {
        int[] data =  {1,3,2,4,6,7,5,9,0,8};
        shellSort(data);
        System.out.println("希尔排序" + Arrays.toString(data));
    }


    public static void shellSort(int[] data) {
        int length = data.length;
        // 决定比较间隔
        for (int i = length/2; i>0; i/=2) {
            // 根据比较间隔将数组分成若干个子数组
            for (int j = i; j < length; j++) {
                // 对若干个子数组进行插入排序
                for (int k = j; k >=i && data[k] < data[k-i] ; k-=i) {
                    int tmp = data[k];
                    data[k] = data[k-i];
                    data[k-i] = tmp;
                }
            }
        }
    }
}

运行以上代码结果如下：