Java排序算法之——希尔排序

Enlightenment 发布于2019-08-14 12:21 / 1497人阅读

摘要：算法简述希尔排序也叫作排序或缩小增量排序，据说是一个叫的人发明出来的，顾取名排序。这种排序是基于插入排序思想的，也比较适用于数据量大时。

算法简述

希尔排序也叫作shell排序或缩小增量排序，据说是一个叫D.L.Shell的人发明出来的，顾取名shell排序。这种排序是基于插入排序思想的，也比较适用于数据量大时。

我刚开始看到时候对于插入排序也是半瓶子醋，直接导致我看不懂了，抓狂，so...我就去默默的补习一下插入排序喽。

插入排序简介

插入排序的核心思想是比较和插入，就是从第二个数开始，依次插入到前面合适的位置。排序步骤如下：

1. 首先对数组的前两个数据进行从小到大的排序
2. 接着将第3个数据与排序好的两个数据进行比较，插入合适的位置
3. 然后，将第4个数据插入已经排好的前3个数据中
4. 不断重复上述的过程，完成排序

代码实现

private void insertSort(int[] a)
    {
        int i,j,t,h;
        for(i =1;i=0&&t
简单的介绍了一下插入排序，下面就讲一下这个希尔排序。
排序步骤
1.将有n个元素的数组分为n/2个数字序列，第1个数据和第n/2+1个数据为一对。。。
2.一次循环使每一个序列对排好顺序（对每个序列使用插入排序算法，实质是一种分组插入）
3.然后，再变为n/4个序列，再次排序
4.不断重复上述过程，随着序列减少最后变为一个，也就完成了整个排序。

实例讲解
比如对{12,31,11,20,17，30}进行希尔排序：
1. 第一次排序，首先将数组分为6/2=3个数字序列，第一个数据12和第四个数据20为一对，第二个数据和第五个数据为一对，第三个数据和第六个数据为一对，每一对进行排序后数据为：12,17,11,20,31,30
2. 第二次排序，将数组划分为6/4=1（这里取整），此时逐个对数据比较，按照插入排序算法进行排序，排序后的数据为：11,12,17,20,30,31

代码片段
private void shellSort(int[] a)
    {
        int i,j,h;
        int r,temp;
        int x = 0;
        for(r = a.length/2;r>=1;r/=2)
        {
            for(i = r;i=0&&temp
至此希尔排序就完成了，时间复杂度为O(nlog2n).

GPU云服务器云服务器希尔排序 java插入排序算法 java实验排序算法 java自然排序算法

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/64424.html

糊涂算法之「八大排序」总结——用两万字，8张动图，450行代码跨过排序这道坎（建议收藏）

摘要：今天，一条就带大家彻底跨过排序算法这道坎，保姆级教程建议收藏。利用递归算法，对分治后的子数组进行排序。基本思想堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序，它的最坏，最好，平均时间复杂度均为，它也是不稳定排序。 ...

greatwhole 2021-09-28 09:36 评论0 收藏0
基本算法学习(一)之希尔排序(JS)

摘要：动态定义间隔序列参考来源详细介绍了十种算法大家可以去学习下以后大概会尽量每天更新一个算法学习吧温故而知新参考书:严蔚敏-数据结构希尔排序(Shells Sort) 希尔排序又称缩小增量排序,归属于插入排序一类,简单来说,和我们的插入排序比,它更快. 奇妙的记忆点: 内排序(内存排序就够了) 不稳定(排序后原始顺序无法保证) 希尔排序重点在于分割. 基本思想: 将整个待排序记录序...

cooxer 2019-08-20 11:09 评论0 收藏0
排序算法（Java）——那些年面试常见的排序算法

摘要：下面会介绍的一种排序算法快速排序甚至被誉为世纪科学和工程领域的十大算法之一。我们将讨论比较排序算法的理论基础并中借若干排序算法和优先队列的应用。为了展示初级排序算法性质的价值，我们来看一下基于插入排序的快速的排序算法希尔排序。前言　　排序就是将一组对象按照某种逻辑顺序重新排列的过程。比如信用卡账单中的交易是按照日期排序的——这种排序很可能使用了某种排序算法。在计算时代早期，大家普遍...

Harpsichord1207 2019-08-15 14:50 评论0 收藏0
七大排序算法总结(java)

摘要：前面介绍了七大算法的思想与实现步骤，下面来做一个归总。直到无序区中的数为零，结束排序。步骤以从小到大为例，排序数组大小为。比较完以后则排序结束。堆排序思想堆排序是采用树的形式的数据结构来进行排序的，其中每一个堆都是完全二叉树。前面介绍了七大算法的思想与实现步骤，下面来做一个归总。排序方法平均复杂度最坏复杂度最好复杂度辅助空间稳定性直接选择排序 O(n^2...

cartoon 2019-08-14 14:09 评论0 收藏0
希尔排序就这么简单

摘要：这时就用简单插入排序将数列直至已序从直观上看希尔排序就是把数列进行分组不停使用插入排序，直至从宏观上看起来有序，最后插入排序起来就容易了无须多次移位或交换。一、希尔排序介绍来源百度百科：希尔排序(Shells Sort)是插入排序的一种又称缩小增量排序（Diminishing Increment Sort），是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方...

paulli3 2019-08-19 10:43 评论0 收藏0