算法-插入排序-希尔排序

标签: 希尔排序

算法-插入排序-希尔排序

基本思想:

算法先将要排序的一组数按某个增量d(n/2,n为要排序数的个数)分成若干组,每组中记录的下标相差d.对每组中全部元素进行直接插入排序,然后再用一个较小的增量(d/2)对它进行分组,在每组中再进行直接插入排序。当增量减到1时,进行直接插入排序后,排序完成。

插图:

这里写图片描述

代码:

import java.util.Arrays;

/**
 * 希尔排序
 * 
 * @author Eyre
 *
 */
public class ShellSort {

    public static void main(String[] args) {
        int[] arr = { 8, 9, 1, 7, 2, 3, 5, 4, 6, 0 };
        System.out.println("初始状态:" + Arrays.toString(arr));
        System.out.println("最终结果:" + Arrays.toString(shellSort(arr)));
    }

    public static int[] shellSort(int[] arrays) {
        // 增量每次都/2
        for (int step = arrays.length / 2; step > 0; step /= 2) {
            // 从增量那组开始进行插入排序,直至完毕
            for (int i = step; i < arrays.length; i++) {
                int j = i;
                int temp = arrays[j];
                // j - step 就是代表与它同组隔壁的元素
                while (j - step >= 0 && arrays[j - step] > temp) {
                    arrays[j] = arrays[j - step];
                    j = j - step;
                }
                arrays[j] = temp;
            }
            System.out.println("过程:" + Arrays.toString(arrays));
        }
        return arrays;
    }

}

运行结果:

初始状态:[8, 9, 1, 7, 2, 3, 5, 4, 6, 0]
过程:[3, 5, 1, 6, 0, 8, 9, 4, 7, 2]
过程:[0, 2, 1, 4, 3, 5, 7, 6, 9, 8]
过程:[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
最终结果:[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
原文链接:加载失败,请重新获取