希尔排序

  1. 希尔排序又称最小增量排序。
  2. 是对插入排序的优化。
  3. 基本思想:选取合理的增量,经过一轮排序后,就会让序列大致有序,然后再不断缩小增量,增量每次缩小为原来的一半,进行插入排序,直到增量为1,排序结束。
  4. 直接插入排序其实就是增量为1的希尔排序。
  5. 第一次增量选取长度的一半。
public class ShellsSort {
    public static void main(String[] args) {
        int[] arr = {46, 55, 13, 42, 17, 94, 5, 70};
        int j;

        // 初始增量为数组长度的一半,每一趟除以2
        for (int h = arr.length / 2; h > 0; h /= 2) {
            // 选择排序
            for (int i = h; i < arr.length; i++) {
                Comparable<Integer> tmp = arr[i];
                for (j = i; j >= h && tmp.compareTo(arr[j - h]) < 0; j -= h) {
                    arr[j] = arr[j - h];
                }
                arr[j] = (int) tmp;
            }
        }
        System.out.println(Arrays.toString(arr));
    }
}
Copyright © rootwhois.cn 2021-2022 all right reserved,powered by GitbookFile Modify: 2022-09-08 15:28:49

results matching ""

    No results matching ""