排序算法图解之Java希尔排序

目录
  • 1.希尔排序简介
  • 2.希尔排序算法图解
  • 3.希尔排序代码实现

1.希尔排序简介

希尔排序是希尔(Donald Shell)于1959年提出的一种排序算法，其也是一种特殊的插入排序，即将简单的插入排序进行改进后的一个更加高效的版本，也称缩小增量排序。

希尔排序是非稳定排序算法。把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至 1 时，整个文件恰被分成一组，算法便终止。

2.希尔排序算法图解

以序列: {8, 9, 1, 7, 2, 3, 5, 6, 4, 0} 为例！

1.初始步长gap = length/2 ＝ 5，意味着将整个数组分为了5组，即[8，3]，[9，5]，[1，6]，[7，4]，[2，0]，对每组进行插入排序，得到序列：{3，5，1，4，0，8，9，6，7，2}，可以看到：3，5，4，0这些小元素都被提到前面了。

2.缩小增量gap = 5/2 = 2，数组被分为两组，即[3，1，0，9，7]，[5，4，8，6，2]，对这两组分别进行直接插入排序，可以看到，整个数组的有序程度更进一步了。

3.再次缩小增量，gap = 2/2 = 1，此时整个数组为[0，2，1，4，3，5，7，6，9，8]，进行一次插入排序，即可实现数组的有序化（仅需要简单微调，而无需大量移动操作）。

3.希尔排序代码实现

import java.util.Arrays;

/**
 * @author 兴趣使然黄小黄
 * @version 1.0
 * 希尔排序
 */
public class ShellSort {

    public static void main(String[] args) {
        int[] arr = {8, 9, 1, 7, 2, 3, 5, 6, 4, 0};
        System.out.println("排序前: " + Arrays.toString(arr));
        shellSort(arr);
        System.out.println("排序后: " + Arrays.toString(arr));
    }

    //希尔排序
    public static void shellSort(int[] arr){
        //设定步长
        for (int gap = arr.length / 2; gap > 0; gap /= 2){
            //将数据分为arr.length/gap组，逐个对其所在的组进行插入排序
            for (int i = gap; i < arr.length; i++) {
                //遍历各组中的所有元素，步长为gap
                int j = i;
                int temp = arr[j]; //记录待插入的值
                while (j - gap >= 0 && temp < arr[j-gap]){
                    //移动
                    arr[j] = arr[j-gap];
                    j -= gap;
                }
                //找到位置，进行插入
                arr[j] = temp;
            }
            System.out.println(Arrays.toString(arr));
        }
    }
}

到此这篇关于排序算法图解之Java希尔排序的文章就介绍到这了,更多相关Java希尔排序内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • Java 十大排序算法之希尔排序刨析

    Java 十大排序算法之希尔排序刨析

    目录 希尔排序原理 希尔排序的API设计 希尔排序的代码实现 希尔排序是插入排序的一种,又称"缩小增量排序",是插入排序算法的一种更高效的改进版本. 希尔排序原理 1.选定一个增长量h,按照增长量h作为数据分组的依据,对数据进行分组. 2.对分好组的每一组数据完成插入排序. 3.减小增长量,最小减为1,重复第二步操作. 希尔排序的API设计 类名 Shell 构造方法 Shell():创建Shell对象 成员方法 1.public static void sort(Comparable

  • 图解Java排序算法之希尔排序

    图解Java排序算法之希尔排序

    目录 基本思想 代码实现 总结 希尔排序是希尔(Donald Shell)于1959年提出的一种排序算法.希尔排序也是一种插入排序,它是简单插入排序经过改进之后的一个更高效的版本,也称为缩小增量排序,同时该算法是冲破O(n2)的第一批算法之一.本文会以图解的方式详细介绍希尔排序的基本思想及其代码实现. 基本思想 希尔排序是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序:随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个文件恰被分成一组,算法便终止. 简单插入排序很循规蹈

  • java数据结构之希尔排序

    希尔排序,也称递减增量排序算法,是插入排序的一种更高效的改进版本.希尔排序是非稳定排序算法. 希尔排序是基于插入排序的以下两点性质而提出改进方法的: 插入排序在对几乎已经排好序的数据操作时,效率高,即可以达到线性排序的效率:         但插入排序一般来说是低效的,因为插入排序每次只能将数据移动一位. 实现: 先取一个正整数d1 < n, 把所有相隔d1的记录放一组,每个组内进行直接插入排序:然后d2 < d1,重复上述分组和排序操作:直至di = 1,即所有记录放进一个组中排序为止. 简

  • java 排序算法之希尔算法

    java 排序算法之希尔算法

    目录 插入排序存在的问题 简单介绍 基本思想 代码实现 大数据量耗时测试 移动法实现希尔排序 移动法-大数据量耗时测试 算法分析 注:学习本篇的前提是要会插入排序,数据结构与算法--排序算法-插入排序 插入排序存在的问题 简单的插入排序可能存在的问题. 如数组 arr = {2,3,4,5,6,1} 这时需要插入的数 1(最小),过程是: 展示的是要移动 1 这个数,的过程,由于在最后,需要前面的所有数都往后移动一位 {2,3,4,5,6,6} {2,3,4,5,5,6} {2,3,4,4,5,

  • 图解Java经典算法希尔排序的原理与实现

    目录 希尔排序 算法思想 图解 代码实现(Java) 希尔排序 希尔排序时插入排序的一种,也称缩小增量排序,是直接插入排序的一种更高效的改进版本.希尔排序是非稳定排序算法. 算法思想 希尔排序是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序,随着增量逐渐减少,每组包含的数越来越多当增量减至1时,整个序列恰好被分成一组,算法完成. 我们以增序排序为例,希尔排序基本步骤:选择初始增量gap=length/2,缩小增量继续以gap=gap/2的方式进行,直到增量gap=1为止,增量的每次变

  • JAVA十大排序算法之希尔排序详解

    JAVA十大排序算法之希尔排序详解

    目录 希尔排序 代码实现 时间复杂度 算法稳定性 总结 希尔排序 一种基于插入排序的快速的排序算法.简单插入排序对于大规模乱序数组很慢,因为元素只能一点一点地从数组的一端移动到另一端.例如,如果主键最小的元素正好在数组的尽头,要将它挪到正确的位置就需要n-1次移动. 希尔排序为了加快速度简单地改进了插入排序,也称为缩小增量排序. 希尔排序是把待排序数组按一定的数量分组,对每组使用直接插入排序算法排序:然后缩小数量继续分组排序,随着数量逐渐减少,每组包含的元素越来越多,当数量减至 1 时,整个数组

  • 排序算法图解之Java希尔排序

    目录 1.希尔排序简介 2.希尔排序算法图解 3.希尔排序代码实现 1.希尔排序简介 希尔排序是希尔(Donald Shell)于1959年提出的一种排序算法,其也是一种特殊的插入排序,即将简单的插入排序进行改进后的一个更加高效的版本,也称缩小增量排序. 希尔排序是非稳定排序算法.把记录按下标的一定增量分组,对每组使用直接插入排序算法排序:随着增量逐渐减少,每组包含的关键词越来越多,当增量减至 1 时,整个文件恰被分成一组,算法便终止. 2.希尔排序算法图解 以序列: {8, 9, 1, 7,

  • 排序算法图解之Java选择排序

    目录 1.选择排序简介 2.图解选择排序算法 3.选择排序代码实现 1.选择排序简介 选择排序(Selection sort)是一种简单直观的排序算法.它的工作原理是:第一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,然后再从剩余的未排序元素中寻找到最小(大)元素,然后放到已排序的序列的末尾.以此类推,直到全部待排序的数据元素的个数为零.选择排序是不稳定的排序方法. 2.图解选择排序算法 选择排序的基本思想如下: 第一次:从arr[0]~arr[n-1]中选取最小值,

  • 排序算法图解之Java插入排序

    排序算法图解之Java插入排序

    目录 1.插入排序简介 2.插入排序思想及图解 3.插入排序代码实现 1.插入排序简介 插入排序,一般也被称为直接插入排序.对于少量元素的排序,它是一个有效的算法.插入排序是一种最简单的排序方法,它的基本思想是将一个记录插入到已经排好序的有序表中,从而一个新的.记录数增1的有序表.在其实现过程使用双层循环,外层循环对除了第一个元素之外的所有元素,内层循环对当前元素前面有序表进行待插入位置查找,并进行移动 2.插入排序思想及图解 插入排序的基本思想如下: 把n个待排序的元素看成为一个有序表和一个无

  • 排序算法图解之Java快速排序的分步刨析

    目录 1.快速排序简介 2.思路简介及图解 3.实现代码及运行结果 1.快速排序简介 快速排序是对冒泡排序的一种改进.基本思想为:通过一趟排序将要排序的数据分割为独立的两个部分,其中一部分的所有数据比另外一部分的所有数据要小,然后按照此方法对这两部分分别进行快速排序,整个过程可以递归进行,以此达到整个数据变成有序序列. 2.思路简介及图解 快速排序算法通过多次比较和交换来实现排序,其排序流程如下: (1)首先设定一个分界值,通过该分界值将数组分成左右两部分. (2)将大于或等于分界值的数据集中到

  • 排序算法图解之Java冒泡排序及优化

    目录 1.冒泡排序简介 2.图解算法 3.冒泡排序代码实现 4.冒泡排序算法的优化 1.冒泡排序简介 冒泡排序(Bubble Sorting)即:通过对待排序的序列从前往后,依次比较相邻元素的值,若发现逆序则交换位置,使较大的元素逐渐移动到后部,就像水底的气泡一样逐渐从水面冒出来,这就是冒泡名称的由来 2.图解算法 以将序列{3, 9, -1, 10, -20}从小到大排序为例! 基本思想就是,在每一趟排序实现将最大的数移到序列的最后端!这主要通过比较相邻两个元素实现,当相邻的两个元素逆序的时候

  • 图解Java经典算法冒泡选择插入希尔排序的原理与实现

    图解Java经典算法冒泡选择插入希尔排序的原理与实现

    目录 一.冒泡排序 1.基本介绍 2.代码实现 二. 选择排序 1.基本介绍 2.代码实现 三.插入排序 1.基本介绍 2.代码实现 四.希尔排序 1.基本介绍 2.代码实现(交换排序) 3.代码实现(移位排序) 一.冒泡排序 1.基本介绍 冒泡排序是重复地走访要排序的元素,依次比较两个相邻的元素,如果它们的顺序与自己规定的不符合,则把两个元素的位置交换.走访元素重复地进行,直到没有相邻元素需要交换为止,完成整个排序过程. 算法原理 1.比较相邻元素,如果前一个元素大于后一个元素,则交换. 2.

  • Java十大经典排序算法图解

    Java十大经典排序算法图解

    目录 0.算法概述 0.1 算法分类 0.2 算法复杂度 0.3 相关概念 1.冒泡排序(Bubble Sort) 1.1 算法描述 1.2 动图演示 1.3 代码实现 2.选择排序(Selection Sort) 2.1 算法描述 2.2 动图演示 2.3 代码实现 2.4 算法分析 3.插入排序(Insertion Sort) 3.1 算法描述 3.2 动图演示 3.3代码实现 3.4 算法分析 4.希尔排序(Shell Sort) 4.1 算法描述 4.2 动图演示 4.3 代码实现 4.

  • 2个java希尔排序示例

    2个java希尔排序示例

    java希尔排序 希尔排序是插入排序的一种类型,也可以用一个形象的叫法缩小增量法.基本思想就是把一个数组分为好几个数组,有点像分治法,不过这里的划分是用一个常量d来控制. 这个0<d<n,n为数组的长度.这个算法有了插入排序的速度,也可以算是一个改进算法,在插入算法中,如果有一个最小的数在数组的最后面,用插入算法就会重最后一个 位置移动到第一个,这样就会浪费很大,使用这个改进的希尔排序可以实现数据元素的大跨度的移动.也就是这个算法的优越之处. 复制代码 代码如下: package cn.cqu

  • 七大经典排序算法图解

    七大经典排序算法图解

    目录 插入排序 ①直接插入排序 基本思想 动图演示 代码实现 ②希尔排序 基本思想 图示 代码实现 选择排序 ③直接选择排序 基本思想 动图演示 代码实现 ④堆排序 基本思想 建堆需要注意的问题 图示 代码实现 交换排序 ⑤冒泡排序 基本思想 动图演示 代码实现 ⑥快速排序 基本思想 基本框架 Partion函数分析 Partion函数的优化 快速排序代码实现 归并排序 ⑦归并排序 基本思想 动图演示 代码实现 排序算法复杂度及稳定性分析 插入排序 ①直接插入排序 基本思想 每次从一个有序序列开

  • JS排序算法之冒泡排序，选择排序与插入排序实例分析

    本文实例讲述了JS排序算法之冒泡排序,选择排序与插入排序.分享给大家供大家参考,具体如下: 冒泡排序: 对数组的中的数据,依次比较相邻两数的大小. 如果前面的数据大于后面的数据,就交换这两个数. 时间复杂度O(n^2) function bubble(array){ var temp; for(var i=0; i<arr.length; i++){ for(var j=0; j<arr.length; j++){ if(arr[j]>arr[j+1]){ temp = arr[j+1]

随机推荐