Android防重复点击 希腊字母 function uitableview github configuration bluetooth vue添加class less用法 多店版微信商城 jquery获取最后一个子元素 float占几个字节 linux管道符 oracle行转列函数 python数据类型转换 hadoop环境变量配置 mysql时间戳转换日期 python环境配置 python或运算 python基础练习 python做界面 python中文教程 java的正则表达式 java链接mysql数据库 java函数调用 php入门例子 简体中文语言包 js删除数组指定元素 oxm idataparameter 微信昵称找人的软件 ps3d字体 截取字符串 淘宝抽奖活动 ps祛痘 cad拉伸命令 谷歌浏览器xp版下载 ps取色 反转字符串 三菱plc序列号
当前位置: 首页 > 学习教程  > 编程语言

十大经典排序算法之希尔排序(Shell Sort)

2020/12/28 20:12:25 文章标签:

希尔排序(Shell Sort) 1959年由唐纳德希尔(Donald Shell)提出希尔排序把序列看作是一个矩阵,分成 𝑚 列,逐列进行排序 从某个整数逐渐减为1 当 𝑚 为1时,整个序列将完全…

希尔排序(Shell Sort)

  • 1959年由唐纳德·希尔(Donald Shell)提出
  • 希尔排序把序列看作是一个矩阵,分成 𝑚 列,逐列进行排序
    从某个整数逐渐减为1
    当 𝑚 为1时,整个序列将完全有序
  • 因此,希尔排序也被称为递减增量排序(Diminishing Increment Sort)
  • 矩阵的列数取决于步长序列(step sequence)
    ✓ 比如,如果步长序列为{1,5,19,41,109,…},就代表依次分成109列、41列、19列、5列、1列进行排序
    ✓ 不同的步长序列,执行效率也不同

(1)希尔排序 — 实例1

  • 希尔本人给出的步长序列是 𝑛/2𝑘,比如 𝑛 为16时,步长序列是{1, 2, 4, 8}
    在这里插入图片描述
  • 分成8列进行排序
    在这里插入图片描述
  • 分成4列进行排序
    在这里插入图片描述
  • 分成2列进行排序
    在这里插入图片描述
  • 分成1列进行排序
    在这里插入图片描述
  • 不难看出来,从8列 变为 1列的过程中,逆序对的数量在逐渐减少
  • 因此希尔排序底层一般使用插入排序对每一列进行排序,也很多资料认为希尔排序是插入排序的改进版

(2)希尔排序 — 实例2

  • 假设有11个元素,步长序列是{1,2,5}
    在这里插入图片描述
  • 假设元素在第 col 列、第 row 行,步长(总列数)是 step
    那么这个元素在数组中的索引是 col + row * step
    比如 9 在排序前是第 2 列、第 0 行,那么它排序前的索引是 2 + 0 * 5 = 2
    比如 4 在排序前是第 2 列、第 1 行,那么它排序前的索引是 2 + 1 * 5 = 7

(3)希尔排序 — 实现

  • 最好情况是步长序列只有1,且序列几乎有序,时间复杂度为 O(n)
  • 空间复杂度为O(1),属于不稳定排序
import org.junit.Test;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

    @Test
    public void ShellSort(){
         class ShellSortTest{

            final int[] array = {3,44,38,5,47,15,36,26,27,2,46,4,19,50,48};
            protected void sort() {
                System.out.println("排序前"+Arrays.toString(array));

                List<Integer> stepSequence = shellStepSequence();
                for (Integer step : stepSequence) {
                    shellSort(step);
                }
                System.out.println("排序后"+Arrays.toString(array));
            }

            /**
             * 分成step列进行排序
             * @param step
             */
            private void shellSort(int step){
                //col:第几列,column的简称
                for (int col = 0; col < step; col++) {//对第col列进行排序

                    //对[0,array.length)范围的元素进行插入排序
                    //col、col+step、col+2step、col+3step....
                    for (int begin = col+step; begin < array.length; begin+=step) {
                        int cur = begin;
                        while (cur > col && (array[cur]-array[(cur-step)])<0){
                            //swap(cur,cur-step);
                            int tmp = array[cur];
                            array[cur] = array[(cur-step)];
                            array[(cur-step)] = tmp;
                            cur -= step;
                        }
                    }
                }
            }

            private List<Integer> shellStepSequence(){
                List<Integer> stepSequence = new ArrayList<>();
                int step = array.length;
                while ((step >>= 1) > 0){
                    stepSequence.add(step);
                }
                return stepSequence;
            }
        }

        ShellSortTest shellSortTest = new ShellSortTest();
         shellSortTest.sort();
    }
}
运行结果:
排序前[3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]
排序后[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

(4)希尔排序 — 步长序列

  • 目前已知的最好的步长序列,最坏情况时间复杂度是 O(n4/3) ,1986年由Robert Sedgewick提出
    在这里插入图片描述
protected void sort() {
    List<Integer> stepSequence = sedgewickStepSequence();
    System.out.println(stepSequence);
    for (Integer step : stepSequence) {
        shellSort(step);
    }
}
//省略代码....
private List<Integer> sedgewickStepSequence() {
	List<Integer> stepSequence = new LinkedList<>();
    int k = 0, step = 0;
    while (true) {
        if (k % 2 == 0) {
            int pow = (int) Math.pow(2, k >> 1);
            step = 1 + 9 * (pow * pow - pow);
        } else {
            int pow1 = (int) Math.pow(2, (k - 1) >> 1);
            int pow2 = (int) Math.pow(2, (k + 1) >> 1);
            step = 1 + 8 * pow1 * pow2 - 6 * pow2;
        }
        if (step >= array.length) break;
        stepSequence.add(0, step);
        k++;
    }
    return stepSequence;
}

本文链接: http://www.dtmao.cc/news_show_550430.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?