基础算法|7 希尔排序 HDU 1425

我们从最初的冒泡排序算法,到上篇文章的折半插入排序算法,我们一共学习了5种排序算法,相信以大家的聪明才智肯定都消化了^_^。在本篇文章中,我们又将学习第6种排序算法——希尔排序算法。那就让我们直奔主题吧。


希尔排序

让我们回想一下直接插入排序算法,是不是每次都是讲一个待排序的元素按顺序插入到一个有序序列中。那我们想,如果整个待排序的序列都是"基本有序"的,而且元素数量较少,是不是直接插入排序的执行效率会更高呢?显然,这是肯定的,希尔排序就是通过这种思想来改进直接插入排序算法。


希尔排序的算法思想

希尔排序通过一个增量序列(最后一个增量必须为1),按逐个增量将待排序序列划分为若干个组,然后对每个组中的两个元素进行排序(第一次改进,使待排序元素数量较少),这样通过每个增量划分成的组通过排序之后,整体序列就成了"基本有序"了(第二次改进,使整个待排序序列整体有序),然后当增量为1时,对整体在进行一次直接插入排序,即得到了有序序列。

tip:增量是指元素间的间隔数,比如序列[4,2,3,6],4与6的增量就是3,因为间隔数为3。

是不是有点难以理解,没事,让我们来个例子演示一下。


希尔排序的实现过程

例如,我们要对序列[8,6,10,13,5,7]进行希尔排序,我可以选取增量序列,d1=3,d2=1。(tip:增量的选取没有明确的规定,笔者较喜欢奇数的增量,只要保证最后一个增量为1即可)。按第一个增量d1分组,我们可以分为3组——8与13,6与5,10与7(间隔数均为3),对每个组进行一次排序,8小于13所以8和13的位置不变;6大于5,所以6与5交换位置,得到序列[8,5,10,13,6,7];同理10大于7,交换位置得到序列[8,5,7,13,6,10]。这样通过第一个增量排序后,我们得到了一个基本有序的数列。之后的增量重复上述操作,直到最后一个增量为1时,对整体在进行一个直接插入排序即可。


代码实现

public static  void shellSort (int[] a){
        int d1 = a.length/2;  //取第一个增量
        if(d1 %2 ==0){ //如果为偶数,则自减变为奇数
            d1 --;
        }
        for(int i=d1;i>=1;i=i-2){ //将第一个增量逐次减2
            if(i == 1){  //若增量为1,则对整个数列直接插入排序
                straightInsertSort(a);
                break;
            }
            for(int j=0;j<i;j++){   //每次将序列划分为增量值的组数(例如增量为3,则分为3组),然后对每个组排序
                if(a[j]>a[j+i]){  //若前面的数大于后面的数
                    a[j] = (a[j]+a[j+i]) - (a[j+i] = a[j]);  //将两数进行交换
                }
            }
        }

    }

    public static void straightInsertSort(int[] a) {
        int elements = 1; //记录结果集中元素的个数,起初只有a[0]这一个元素
        for(int i=1;i<a.length;i++){  //从a[1]开始逐个插入
            int j;
            for(j=0;j<elements;j++){  //遍历结果集,逐次与a[i]作比较
                if(a[j] > a[i]){  //若a[j] >a[i],则把结果集从最后位置(即a[elements-1])到j位置逐个向后移动一个位置
                    int temp = a[i]; //将要插入的值保留到temp中
                    for(int k =elements-1;k>=j;k--){
                        a[k+1] = a[k];
                    }
                    a[j] = temp;    //将要插入的值插入到j位置
                    elements++; //结果集元素的个数加1
                    break;
                }
            }
            if(j == elements){  //说明结果集中的元素都小于等于a[i],即将a[i]的值插入到末尾
                a[elements] = a[i];
                elements++;
            }

        }
    }
</elements;j++){  </a.length;i++){  </i;j++){   

让我们来测试一下我们的算法吧

public static void main(String[] args) {
        int[] a = new int[]{8,10,6,19,17,3,13,16};
        shellSort(a);
        for(int i :a){
            System.out.print(i+"  ");
        }
    }

我们又来到了我们的老规矩时间,上题~


HDU 1425 sort

Problem Description

给你n个整数,请按从大到小的顺序输出其中前m大的数。

Input

每组测试数据有两行,第一行有两个数n,m(0<n,m<1000000),第二行包含n个各不相同,且都处于区间[-500000,500000]的整数。< p=""></n,m<1000000),第二行包含n个各不相同,且都处于区间[-500000,500000]的整数。<>

Output

对每组测试数据按从大到小的顺序输出前m大的数。

Sample Input

5 3 
3 -35 92 213 -644

Sample Output

213 92 3

分析:是不是感觉so easy呢~只要我们先对这个序列进行希尔排序,然后从后往前输出m个数即可。

代码实现:

public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int n, m; // 输入元素数量n,和输出前m大的数中的m
        n = input.nextInt();
        m = input.nextInt();
        do {
            if (n <= 0 || n >= 1000000 || m <= 0 || m >= 1000000) {
                System.out.println("请重新输入");
                n = input.nextInt();
                m = input.nextInt();
            }
            else{
                break;
            }
        } while (true);
        int[] a = new int[n];
        for (int i = 0; i < n; i++) { // 输入元素
            a[i] = input.nextInt();
            if(a[i]<-500000 || a[i]>500000){
                System.out.println("请重新输入:");
                a[i] = input.nextInt();
            }
        }
        shellSort(a);
        for (int i = n - 1; i >= n - m; i--) {
            System.out.print(a[i] + "  ");
        }
    }

让我们来测试一下吧


总述

本篇文章我们学习了第6种排序算法——希尔排序,我们可以将其与之前所学习的算法进行比较式学习,这样学习的效率的更佳呢ヾ(◍°∇°◍)ノ゙

点赞的时候,请宠溺一点

原文发布于微信公众号 - ACM算法日常(acm-clan)

原文发表时间:2018-10-23

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏cmazxiaoma的架构师之路

一个Java小白通向数据结构算法之旅(6) - 插入排序

19650
来自专栏软件开发 -- 分享 互助 成长

经典算法学习之分治法(以排列、组合程序为例)

分治法的思想:将原问题分解为几个规模较小但类似于原问题的子问题,递归的求解这些子问题,然后再合并这些子问题的解来建立原问题的解。 分治法在每层递归是遵循的三个步...

44170
来自专栏Python中文社区

Python数组中求和问题

本专题主要介绍哈希表和指针两种方法来解决该类问题,从两个数之和引申到三个数之和,再从四个数之和的问题上思考如何构建出一种通用的代码(可以解决N个数之和)。本文主...

39000
来自专栏Java帮帮-微信公众号-技术文章全总结

Java基础-day09-重构随机点名器

Java基础-day09-重构随机点名器 1.案例介绍与演示 随机点名的案例由之前简单的Person对象,重构为相对完整的Person对象并使用。 2.案例回顾...

51560
来自专栏编程理解

排序算法(九):桶排序

桶排序是将待排序集合中处于同一个值域的元素存入同一个桶中,也就是根据元素值特性将集合拆分为多个区域,则拆分后形成的多个桶,从值域上看是处于有序状态的。对每个桶中...

12720
来自专栏python学习之旅

算法笔记(八):复杂度分析(二)

#感兴趣的可以去订阅极客时间前谷歌工程师的专栏:数据结构与算法之美,个人觉得写的很不错。这里只是我自己做的一个简单的笔记

16520
来自专栏数据小魔方

左手用R右手Python系列7——排序

排序可能是日常数据清洗过程中比较高频的应用了,今天这一篇给大家介绍R语言和Python中最为常见的排序函数应用。 R语言: sort order rank ar...

31040
来自专栏目标检测和深度学习

常用排序算法总结(1)

14220
来自专栏数据结构与算法

P3709 大爷的字符串题(50分)

题目背景 在那遥远的西南有一所学校 /*被和谐部分*/ 然后去参加该省省选虐场 然后某蒟蒻不会做,所以也出了一个字符串题: 题目描述 给你一个字符串a,每次询问...

35270
来自专栏用户画像

7.6.1 内部排序算法的比较

1、简单选择排序、直接插入排序和冒泡排序的平均情况下的时间复杂度都为O(n^2),并且实现过程比较简单,但直接插入排序和冒泡排序在最好的情况下时间复杂度可以达到...

7720

扫码关注云+社区

领取腾讯云代金券