devbox
秋刀鱼在做梦
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

数据结构与算法(14):希尔排序及其实例讲解_希尔排序算法实例讲解

作者：秋刀鱼在做梦 | 2024-07-27 16:30:16

赞

踩

希尔排序算法实例讲解

  在上一个关于算法的博客中我们谈到了插入排序,从时间复杂度来说确实会比冒泡好的太多,但是插入排序是会存在问题的,首先我们看下一个简单的插入排序,进行问题复现
举例:数组arr ={2,3,4,5,6,1 } 当需要插入的数最小为1时,插入排序的过程是:
{2,3,4,5,6,6} ->
{2,3,4,5,5,6} ->
{2,3,4,4,5,6} ->
{2,3,3,4,5,6} ->
{2,2,3,4,5,6} ->
{1,2,3,4,5,6}.我们最终会发现当需要插入的数是较小的数是,后移的次数明显增多,这样的排序对效率是有影响的,为了避免,我们引入了希尔排序.
  下面进入正题:希尔排序

希尔排序

  希尔排序是希尔在1959年提出的一种排序算法,希尔排序也是一种插入排序,它是简单插入排序经过改进之后的一个更高效的版本,也被称为缩小增量排序

希尔排序基本思想
  希尔排序就是把记录按下标进行一定的增量分组,对每组使用直接插入排序算法排序;随着增量逐渐减少,每组包含的关键粗越来越多,当增量减到1时,整个文件恰好被分成一组,算法便终止.

在这里插入图片描述
  我们来看下这个图中的数,首先0放到最后面了,也就是说这里用简单的插入排序会有需要移动很多步,所以我们这里用插入排序
步骤:

  1. 这里有10个数据,分成5组,每两个进行比较,
  2. 比较完毕之后进行缩小增量操作,5/2 =2所以,数据又被分成两组
  3. 然后对上面的两组再分别进行直接插入排序,这样整个数组就更有序写,最后再缩小增量2/2=1,这样整个数组就为1组,直接进行简单的插入排序
  4. 最后数组就有序了.
    优点:经过简单的微调之后,无需大量的移动操作就可以完成整个数组的排序.

代码展示:

package com.qiu.sort;

import java.util.Arrays;

public class ShellSort {
    public static void main(String[] args) {
    int[] arr = {8,9,1,7,2,3,5,4,6,0};
    shellSort(arr);
    }
    //使用逐步推导的方式来执行我们的希尔排序
    //1.希尔排序时,对有序序列在插入时采用交换法,并执行测试的速度
    //2.希尔排序时,对有序序列在插入时采用移动法,并测试执行的速度,效率较高,不好理解

    //使用逐步推导的方式编写shell排序
    public static void shellSort(int[] arr){
        int temp = 0;
        //希尔的第一轮排序
        //因为希尔是第一轮排序,所以分成5组
        for (int i = 5; i <arr.length ; i++) {
            //遍历各组中的所有的元素(共有五组,每一组有两个元素,所以步长是5)
            for (int j =i-5 ; j >=0 ; j-=5) {
                //如果当前的元素大于加上步长后的那个元素,说明需要交换
                if (arr[j]>arr[j+5]){
                    temp = arr[j];
                    arr[j] = arr[j+5];
                    arr[j+5] = temp;
                }
            }
        }
        System.out.println("希尔排序一轮后:"+ Arrays.toString(arr));
        //希尔的第二轮排序
        //因为希尔是第一轮排序,所以分成5组
        for (int i = 2; i <arr.length ; i++) {
            //遍历各组中的所有的元素(共有五组,每一组有两个元素,所以步长是5)
            for (int j =i-2 ; j >=0 ; j-=2) {
                //如果当前的元素大于加上步长后的那个元素,说明需要交换
                if (arr[j]>arr[j+2]){
                    temp = arr[j];
                    arr[j] = arr[j+2];
                    arr[j+2] = temp;
                }
            }
        }
        System.out.println("希尔排序二轮后:"+ Arrays.toString(arr));

        //希尔的第二轮排序
        //因为希尔是第一轮排序,所以分成5组
        for (int i = 1; i <arr.length ; i++) {
            //遍历各组中的所有的元素(共有五组,每一组有两个元素,所以步长是5)
            for (int j =i-1 ; j >=0 ; j-=1) {
                //如果当前的元素大于加上步长后的那个元素,说明需要交换
                if (arr[j]>arr[j+1]){
                    temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }
        }
        System.out.println("希尔排序三轮后:"+ Arrays.toString(arr));
    }

}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63

代码运行显示:
在这里插入图片描述以上就是推导过程,逐步分析可以知道.

package com.qiu.sort;

import java.util.Arrays;

public class ShellSort {
    public static void main(String[] args) {
    int[] arr = {8,9,1,7,2,3,5,4,6,0};
    shellSort(arr);
    }
    //使用逐步推导的方式来执行我们的希尔排序
    //1.希尔排序时,对有序序列在插入时采用交换法,并执行测试的速度
    //2.希尔排序时,对有序序列在插入时采用移动法,并测试执行的速度,效率较高,不好理解

    //使用逐步推导的方式编写shell排序
    public static void shellSort(int[] arr){
        int temp = 0;
        int count = 0;
        for (int gep = arr.length/2; gep > 0; gep=gep/2) {

            for (int i = gep; i <arr.length ; i++) {
                //遍历各组中的所有的元素(共有gep组,每一组有两个元素,所以步长是gep)
                for (int j =i-gep ; j >=0 ; j-=gep) {
                    //如果当前的元素大于加上步长后的那个元素,说明需要交换
                    if (arr[j]>arr[j+gep]){
                        temp = arr[j];
                        arr[j] = arr[j+gep];
                        arr[j+gep] = temp;
                    }
                }
            }
            System.out.println("希尔排序第"+(++count)+"轮后:"+ Arrays.toString(arr));
        }


       
    }

}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39

代码运行展示:
在这里插入图片描述

这样的话就简化了代码,这里用的是交换法,但是这样的效率并不是特别高
检验:同样用八万个数据进行时间检测

public static void main(String[] args) {
        //测试一下冒泡排序的速度,给8w随机数组
        int[] arr = new int[80000];
        for (int i = 0; i < 80000; i++) {
            arr[i] =(int)(Math.random()*80000000);

        }
        //测试排序时间
        Date date = new Date();
        SimpleDateFormat format = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
        String dateStr = format.format(date);
        System.out.println("排序前的时间:"+dateStr);
        shellSort(arr);

        Date date1 = new Date();
        SimpleDateFormat format1 = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
        String dateStr1 = format1.format(date1);
        System.out.println("排序后的时间:"+dateStr1);
    }

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19

代码运行显示:
在这里插入图片描述
大概7秒的样子,原因就是说我们发现一个数就交换,这样并没有用到之前插入排序的移位法进行排序,下面我们在进行对希尔排序的优化
所以我们这里采用希尔排序的移动法

 public static  void shellSort2(int[] arr){
        //这里进行一个希尔排序的移位法进行排序
        //这里也会应用到增量缩减的gep,并足部缩小增量
        for (int gep = arr.length/2; gep > 0; gep=gep/2) {
            //从第gep和元素,逐个对其所在的组进行直接插入排序
            for (int i = gep; i <arr.length ; i++) {
                int j = i;//保存待插入的下标
                int temp = arr[j];//保存待插入的值
                if (arr[j]<arr[j-gep]){
                    while(j-gep>=0&&temp<arr[j-gep]){//如果说下标减去步长还是大于0的,并且待插入的数还是小于这个前一个步长的数,执行以下操作
                        //移动
                        arr[j] = arr[j-gep];//上述条件,满足后,就开始进行赋值,也就是移动操作
                        j-=gep;//然后gep步长--
                    }
                    //当退出while循环后,就给temp找到了位置
                    arr[j] = temp;

                }

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18

代码运行如下图:
在这里插入图片描述这个速度跟上面比起来,真的快的太多了.

上面案例的完整代码:

package com.qiu.sort;

import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;

public class ShellSort {
    public static void main(String[] args) {
        //测试一下冒泡排序的速度,给8w随机数组
        int[] arr = new int[80000];
        for (int i = 0; i < 80000; i++) {
            arr[i] =(int)(Math.random()*80000000);

        }
        //测试排序时间
        Date date = new Date();
        SimpleDateFormat format = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
        String dateStr = format.format(date);
        System.out.println("排序前的时间:"+dateStr);
        shellSort2(arr);

        Date date1 = new Date();
        SimpleDateFormat format1 = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
        String dateStr1 = format1.format(date1);
        System.out.println("排序后的时间:"+dateStr1);
    }
    //使用逐步推导的方式来执行我们的希尔排序
    //1.希尔排序时,对有序序列在插入时采用交换法,并执行测试的速度
    //2.希尔排序时,对有序序列在插入时采用移动法,并测试执行的速度,效率较高,不好理解

    //使用逐步推导的方式编写shell排序
    public static void shellSort(int[] arr){
        int temp = 0;
        int count = 0;
        for (int gep = arr.length/2; gep > 0; gep=gep/2) {

            for (int i = gep; i <arr.length ; i++) {
                //遍历各组中的所有的元素(共有gep组,每一组有两个元素,所以步长是gep)
                for (int j =i-gep ; j >=0 ; j-=gep) {
                    //如果当前的元素大于加上步长后的那个元素,说明需要交换
                    if (arr[j]>arr[j+gep]){
                        temp = arr[j];
                        arr[j] = arr[j+gep];
                        arr[j+gep] = temp;
                    }
                }
            }
            //System.out.println("希尔排序第"+(++count)+"轮后:"+ Arrays.toString(arr));
        }


       
    }
    public static  void shellSort2(int[] arr){
        //这里进行一个希尔排序的移位法进行排序
        //这里也会应用到增量缩减的gep,并足部缩小增量
        for (int gep = arr.length/2; gep > 0; gep=gep/2) {
            //从第gep和元素,逐个对其所在的组进行直接插入排序
            for (int i = gep; i <arr.length ; i++) {
                int j = i;//保存待插入的下标
                int temp = arr[j];//保存待插入的值
                if (arr[j]<arr[j-gep]){
                    while(j-gep>=0&&temp<arr[j-gep]){//如果说下标减去步长还是大于0的,并且待插入的数还是小于这个前一个步长的数,执行以下操作
                        //移动
                        arr[j] = arr[j-gep];//上述条件,满足后,就开始进行赋值,也就是移动操作
                        j-=gep;//然后gep步长--
                    }
                    //当退出while循环后,就给temp找到了位置
                    arr[j] = temp;

                }
            }


        }
    }

}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
声明：本文内容由网友自发贡献，转载请注明出处：【wpsshop】
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号