Java实现希尔排序

发布于 2021-07-30  50 次阅读


希尔排序 就是插入排序 优化版,先用增量分组再对每个分组执行插入排序操作

package com.apesblog.sort.shell;

public class Shell {

    public static void sort(Comparable[] a) {
        int increment = 1;
        while (increment < a.length / 2) {
            increment = increment * 2 + 1;
        }
        while (increment >= 1) {
            for (int i = increment; i < a.length; i++) {
                if (greater(a[i - increment], a[i])) {
                    Comparable t = a[i];
                    int j;
                    for (j = i - increment; j >= 0 && greater(a[j], t); j = j - increment) {
                        a[j + increment] = a[j];
                    }
                    a[j + increment] = t;
                }
            }
            increment = increment / 2;
        }

    }

    private static boolean greater(Comparable i, Comparable j) {
        return i.compareTo(j) > 0;

    }

//    private static void exch(Comparable[] a, int i, int j) {
//        Comparable t = a[i];
//        a[i] = a[j];
//        a[j] = t;
//    }

}
package com.apesblog.sort.shell;

import java.util.Arrays;

public class Test {

    public static void main(String[] args) {
        Integer[] a = { 4, 5, 6, 3, 2, 1 };
        Shell.sort(a);
        System.out.println("希尔排序:" + Arrays.toString(a));
        
        String[] str = { "d", "e", "f", "c", "b", "a" };
        Shell.sort(str);
        System.out.println("希尔排序:" + Arrays.toString(str));

    }

}