希尔排序（Shell Sort）java实现

import java.util.Arrays;

/**
 *
 * @author Shine
 */
public class ShellSort {
    // 希尔排序：在直接插入排序的基础上进行的优化，直接插入排序在n值小的时候效率比较高，
    // 在n很大的时候如果待排序序列基本有序，效率依然很高，时间效率可以提升为O(n)。希尔排序也称之为缩小增量排序。

    public static double[] ShellSort(double data[]) {
        // 先选取一个小于n的整数d（增量），然后按照增量d将待排序序列分为d组，从第一个记录开始间隔为d的为一个组。
        // 然后对各组内进行直接插入排序，一趟过后，间隔为d的序列有序，随着有序性的改善，减少d重复进行。
        // 直到d=1使得间隔为1的记录有序，也就达到了整体有序

        for (int increment = data.length / 2; increment > 0; increment /= 2) {
            for (int i = increment; i < data.length; i++) {
                int j = i - increment;
                double temp = data[i];
//                for (j = i - increment; j >= 0; j -= increment) {
//                    if (temp < data[j]) {
//                        data[j + increment] = data[j];
//                    } else {
//                        break;
//                    }
//                }
                while (j >= 0 && data[j] > temp) {
                    data[j + increment] = data[j];
                    j -= increment;
                }
                data[j + increment] = temp;
            }
            System.out.println(\"increment=\" + increment + \"  =>  \" + Arrays.toString(data));
        }

        return data;
    }

    public static void main(String[] args) {
        double[] arr = new double[]{1.5, 0.7, 3.4, -1.6, 2.3, -0.4, 0, 1.02};
        System.out.println(Arrays.toString(ShellSort(arr)));
    }
}