首页 > 编程语言 > 详细

希尔排序详解

时间:2021-06-02 00:05:10      阅读:38      评论:0      收藏:0      [点我收藏+]

希尔排序详解

说明

  1. 希尔排序是对插入排序的一种升级算法,补足的插入排序的缺点,即如果最小的数字在最末尾,那么插入排序就要交换元素 len - 1次才能将最小元素移动到最前边
  2. 希尔排序也称缩小增量排序,核心思想就是不断的缩小增量,第一次增量缩小为数组元素长度的一半,第二次再缩小一半,以此类推,直到增量缩小到一为止,增量缩小到1也就变成了插入排序,不过之前的n次缩小增量已经基本保证了数组中的小元素在数组前边,大元素在数组后边,移位的次数大大减少
  3. 希尔排序有两种实现方式,即交换法和移位法,交换法就是直接将按增量分组后的元素,判断如果前边的大于后边的则直接交换位置,效率较低,而 移位法类似于插入排序的移位,先寻找要插入的位置,再通过移位插入,效率较高
  4. 源码及详解见下

源码及分析

交换法
/**
     * 希尔排序,也称缩小增量排序
     * 交换法
     * @param arr 要排序的数组
     */
    public static void shellSort(int[] arr) {
        //定义增量step
        int step = arr.length;
        //定义临时变量用于辅助交换
        int tmp = 0;
        //增量每次都变为原来的一半,直到增量为1为止
        while ((step = step / 2) >= 1) {
            //以增量大小为一组将数组元素分组,依次按对应顺序比较对应位置的元素大小
            for (int i = step; i < arr.length; i++) {
                for (int j = i - step; j >=0; j -= step) {
                    //如果后边一组的元素大于前边一组的元素,则交换位置
                    if (arr[j] > arr[j + step]) {
                        tmp = arr[j];
                        arr[j] = arr[j + step];
                        arr[j + step] = tmp;
                    }
                }
            }
        }
    }
移位法
/**
     * 希尔排序之 移位法
     * @param arr 要排序的数组
     */
    public static void shellSort2(int[] arr){
        //变量step为增量,并不断的缩小增量,直到缩小到1为止
        for (int step = arr.length / 2; step > 0; step /= 2) {
            //对每次缩小的增量按照大小进行移位
            for (int i = step; i < arr.length ; i++) {
                //定义变量保存当前要比较的数值及其对应的索引
                int j = i;
                int tmp = arr[j];
                //如果当前数字小于前边一组对应的数字,则移位
                if (arr[j - step] > arr[j]) {
                    //循环寻找当前元素要插入的位置
                    while ((j - step) >= 0 && arr[j - step] > tmp) {
                        arr[j] = arr[j - step];
                        j -= step;
                    }
                    //则循环结束后找到要插入的位置
                    arr[j] = tmp;
                }
            }
        }

    }

希尔排序详解

原文:https://www.cnblogs.com/mx-info/p/14838791.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!