精华内容
下载资源
问答
  • 希尔排序及其代码实现(Java)
    2021-04-23 11:47:40

    希尔排序的介绍

    希尔排序,也称递减增量排序算法,是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。

    希尔排序是基于插入排序的以下两点性质而提出改进方法的:插入排序在对几乎已经排好序的数据操作时,效率高,即可以达到线性排序的效率;

    但插入排序一般来说是低效的,因为插入排序每次只能将数据移动一位;

    希尔排序的基本思想

    希尔排序的基本思想是:先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序,待整个序列中的记录“基本有序”时,再对全体记录进行依次直接插入排序。

    算法步骤选择一个增量序列 t1,t2,……,tk,其中 ti > tj, tk = 1;

    按增量序列个数 k,对序列进行 k 趟排序;

    每趟排序,根据对应的增量 ti,将待排序列分割成若干长度为 m 的子序列,分别对各子表进行直接插入排序。仅增量因子为 1 时,整个序列作为一个表来处理,表长度即为整个序列的长度。

    代码实现import java.util.Arrays;

    public class ShellSort {

    public static void main(String[] args) {

    int[] arr = new int[] { 6, 12, -5, 7, 10, 3 };

    System.out.println("希尔排序前");

    System.out.println(Arrays.toString(arr));

    shellSort(arr);

    System.out.println("希尔排序后");

    System.out.println(Arrays.toString(arr));

    }

    public static void shellSort(int[] arr) {

    int gap, i, j, tmp; // 定义三个变量

    for (gap = arr.length / 2; gap >= 1; gap /= 2) { // 对数组进行划分

    for (i = gap + 1; i < arr.length; i++) { // 从gap往后,进行划分数组

    if (arr[i] < arr[i - gap]) { // 欲插入的元素小于前驱结点元素

    tmp = arr[i]; // 将欲插入元素保存起来

    for (j = i - gap; j >= 0 && tmp < arr[j]; j -= gap) {

    //将前面元素进行后移操作

    arr[j + gap] = arr[j];

    }

    arr[j + gap] = tmp;

    }

    }

    }

    }

    }

    更多相关内容
  • 希尔排序代码

    2015-10-06 22:05:00
    希尔排序(Shell Sort)是插入排序的一种。也称缩小增量排序,是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因DL.Shell于1959年提出而得名。 希尔排序是把记录按下标的一定增量分组,...
  • 希尔排序python代码

    2018-05-16 20:25:18
    希尔排序是插入排序的优化,本资源是希尔排序python代码
  • 希尔排序的算法代码

    2020-09-05 13:51:16
    希尔排序也是一种插入排序方法,实际上是一种分组插入方法。
  • 希尔排序代码实现

    2022-03-29 14:18:21
    希尔排序(Shell Sort)是插入排序的一种算法,是对直接插入排序的一个优化,也称缩小增量排序。希尔排序是非稳定排序算法。 希尔排序是基于直接插入排序的以下两点性质而提出的改进方法: 1.插入排序在对几乎已经排好...

    排序算法总结:

    1. 快速排序
    2. 堆排序
    3. 选择排序
    4. 希尔排序
    5. 冒泡排序
    6. 计数排序
    7. 桶排序
    8. 基数排序
    9. 插入排序
    10. 归并排序

    希尔排序(Shell Sort)插入排序的一种算法,是对直接插入排序的一个优化,也称缩小增量排序。希尔排序是非稳定排序算法。

    希尔排序是基于直接插入排序的以下两点性质而提出的改进方法:
    1.插入排序在对几乎已经排好序的数据操作时,效率高,即可以达到线性排序的效率。
    2.插入排序一般来说是低效的,因为插入排序每次只能将数据移动一位。

    思想:希尔排序是将待排序的数组元素 按下标的一定增量分组 ,分成多个子序列,然后对各个子序列进行直接插入排序算法排序;然后依次缩减增量再进行排序,直到增量为1时,进行最后一次直接插入排序,排序结束。

    在这里插入图片描述
    时间复杂度情况如下:(n指待排序序列长度)

    1. 最好情况:序列是正序排列,在这种情况下,需要进行的比较操作需(n-1)次。后移赋值操作为0次。即O(n)

    2. 最坏情况:**O(nlog2n)。

    3. 渐进时间复杂度(平均时间复杂度):O(nlog2n)

    希尔排序是按照不同步长对元素进行插入排序,当刚开始元素很无序的时候,步长最大,所以插入排序的元素个数很少,速度很快;当元素基本有序了,步长很小,插入排序对于有序的序列效率很高。所以,希尔排序的时间复杂度会比O(n²)好一些。

    希尔排序是不稳定的,这个想必也不同过多解释,因为元素的交换不再是临近元素,而是越过一个间隔,这个间隔中如果有相同值的元素,那么就会造成不稳定。

    Python实现:

    def shellSort(arr):
        l = len(arr)
        if l <= 1:
            return arr
        interVal = l//2
        while interVal >= 1:
            for i in range(l-interVal):
                if arr[i]>arr[i+interVal]:
                    arr[i], arr[i+interVal] = arr[i+interVal], arr[i]
            interVal //= 2
    
    展开全文
  • c代码-排序:希尔排序
  • cpp代码-排序算法之希尔排序
  • 主要介绍了java 算法之希尔排序详解及实现代码的相关资料,需要的朋友可以参考下
  • 1959年Shell发明,第一个突破O(n2)的排序算法,是直接插入排序的改进版。它与插入排序的不同之处在于,它会优先比较距离较远的元素。...下面是希尔排序代码演示,所有的注释都在代码里。 为了辅助理解

    1959年Shell发明,第一个突破O(n2)的排序算法,是直接插入排序的改进版。它与插入排序的不同之处在于,它会优先比较距离较远的元素。希尔排序又叫缩小增量排序。
    希尔排序的大致思路是把数组的元素按照一定的间隔进行逻辑分组,分组后针对每一组进行插入排序。并且渐渐减小间隔,随着间隔的缩小,整个数组就变得越来越有序。这个间隔叫做希尔增量。
    希尔排序的时间复杂度难以测算,大概是O(n^(1.3—2))这么一个范围。
    希尔排序是一种不稳定的排序算法。
    在这里插入图片描述
    下面是希尔排序的代码演示,所有的注释都在代码里。
    为了辅助理解,我在文末加入了插入排序的代码和注释,建议两个排序配合着看,看上几遍基本就懂了

    public static void ShellSort(int[] array)
            {
               int n = array.Length;
                int inc;//希尔增量
                //这里采用朴素希尔增量,就是每次增量都是原来的一半,直到增量为1为止
                for (inc = n / 2; inc >= 1; inc = inc / 2)
                {//每一次循环都通过不断缩短增量达到排序的效果
                    //在一次循环内,inc的值是固定的
                    //下面的内容和插入排序的原理是一样的,只不过每个待排序元素的间隔是inc
                    for (int i = inc; i < n; i++)
                    {//i为什么是从inc开始,而不是从0开始?
                     //因为插入排序中把排序元素分为两组,A组为已排好序的,B组为未排好序要插入的
                     //A组开始时往往是第一个元素(0),那么B组的第一个元素就是整个待拍序列的第二个元素了(inc)
                        int temp = array[i];//temp存储要插入的值
                        int j;
                        for (j = i-inc; j >= 0 && array[j] > temp; j = j - inc)
                        {//j从i-inc开始往前遍历,每一步的距离是inc
                            array[j+inc] = array[j];如果当前遍历到的元素(这里说的遍历到的元素是(array[j])比待插入元素temp小,
                                                      //这个元素往后移动一位,后边的元素被元素覆盖
                                                      //一旦不满足条件,1.说明要么遍历到元素比temp小,这个时候所有比temp大的元素都后移完了
                                                      //2.遍历到头了,此时第一个元素就是要插入的地方
                        }
                        array[j+inc] = temp;
                                        //那么此时array[j+inc]也就是要插入的地方,把temp插入进去
                    }
                }
            }
    

    下边直接插入排序的代码:

    			//插入排序,时间复杂度为O(n²),且是稳定的排序算法
     public static void InsertSort(int[] array)
            {
                //将数组分为两组,一组是已经排好序的(我们称为A组)另一组是还没有排好序的(称为B组)
                //在数组的刚开始,我们把数组的第一个元素array[0]将入A组,剩下的放入B组
                //从数组的第二个元素开始,逐步与A组的元素相比较(从A组的后边往前边比较)
                for (int i = 1; i < array.Length; i++)
                {
                    int temp = array[i];//定义temp存储要插入的值
                    int j;
                    for (j = i-1; j>=0 && array[j]>temp; j--)//将temp逐步与A组的元素(array[j])相比较(从A组的后边往前边比较)
                    {
                        array[j + 1] = array[j];//如果A组中的值大于要比较的值,A组就整个数组往后移动一个位置
                        //这样的移动当然会覆盖A组后边的那个元素的值,
                        //但是别忘了A组后边的那个元素,是要插入的值原本的位置,
                        //所以往后移动只会覆盖这个位置,不会对整个数组产生影响
                    }
                    array[j + 1] = temp;
                    //退出上边的for循环有两种可能
                    //1.在A组中找到了一个比temp小的元素,那么temp就可以插入在这个元素的后边,即array[j+1]的位置
                    //2.全部遍历完毕,在A组中没有找到比这个temp更小的元素,此时应该把temp插入在A组的最前边(array[0])
                    //由于此时j退出循环时候的值为-1,array[j+1]为要插入的位置
                }
            }
    

    可以看出的是,希尔排序在第一个for循环之后的代码基本就和插入排序一样了,所谓的区别只是插排中的"1"变成了inc而已

    展开全文
  • 本文实例讲述了Python实现希尔排序算法的原理与用法。分享给大家供大家参考,具体如下: 希尔排序(Shell Sort)是插入排序的一种。也称缩小增量排序,是直接插入排序算法的一种更高效的改进版本。 希尔排序的基本思想...
  • 希尔排序详解与代码实现 1.简单介绍 希尔排序是希尔(Donald Shell)于1959年提出的一种排序算法。希尔排序也是一种插入排序;它是简单插入排序经过改进之后的一个更高效的版本,也称为缩小增量排序。 看希尔排序前,...

    希尔排序详解与代码实现

    1.简单介绍

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

    看希尔排序前,建议先弄懂插入排序。关于插入排序可以看博主的这篇文章:https://blog.csdn.net/ltf971101/article/details/113767434

    2.基本思想

    希尔排序是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序;随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个文件恰被分成一组,算法便终止。就是将数据进行分组插入排序,这样防止出现在后面的较小数需要经过多次比较移动来找到正确位置。

    3.过程图解

    希尔排序

    4.代码实现(java实现,和插入排序类似,只是增加了分组的过程。)

    private static void shellSort(int[] nums) {
        int n = nums.length;
        // 分组区间 range  需要逐步缩小这个range 分组逐渐变少 整个数组逐渐有序
        for (int range = n / 2; range > 0; range /= 2) {
            for (int i = range; i < n; i++) {
                int j = i;
                int tmp = nums[j];
                if (nums[j] < nums[j - range]) {
                    while (j - range >= 0 && tmp < nums[j - range]) {
                        nums[j] = nums[j - range];
                        j -= range;
                    }
                    nums[j] = tmp;
                }
            }
        }
    }
    

    输入:{8, 9, 1, 7, 2, 3, 5, 4, 6, 0}

    输出:

    第1轮希尔排序中间结果:[3, 5, 1, 6, 0, 8, 9, 4, 7, 2]
    第2轮希尔排序中间结果:[0, 2, 1, 4, 3, 5, 7, 6, 9, 8]
    第3轮希尔排序中间结果:[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
    最终排序结果:[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

    可以结合这个结果和上面的流程图解来理解代码。

    5.总结

    建议先看完插入排序在看希尔排序 会帮助理解。

    展开全文
  • 希尔排序,也称递减增量排序算法,是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。 希尔排序是基于插入排序的以下两点性质而提出改进方法的: 插入排序在对几乎已经排好序的数据操作时,效率高,即...
  • 希尔排序是直接插入排序的一种更高效的改进版本。它把记录按下标的一定增量进行分组,然后对每组使用直接插入排序;随着增量逐渐减少每组中包含的元素越来越多,也越来越有序,当增量减到为1时,整个序列就是一组,...
  • 希尔排序代码 标准C实现 适合初学者了解原理机制
  • 希尔排序代码详解

    2020-08-04 00:59:03
    希尔排序一个重要性质: 后使用的增量排序不会影响之前使用的增量排序 也就是:h1-排序后,不会影响hk排序的成果,否则就是前功尽弃了。。后面排序摧毁了前面的劳动 以Shell建议的序列ht【N/2】和hk【hk+1/2】为例。 ...
  • 希尔排序是对插入排序的一种改进版本,算法本身并不稳定,存在优化空间,这里我们来讲一下希尔排序的大体思路及Swift编程中实现希尔排序算法的代码实例
  • Java代码实现希尔排序
  • 上篇叙述了一下插入排序,希尔排序是建立在插入排序上的一种改进算法。 完整代码 public class Xier { public static void main(String[] args) { int[] arr = new int[100000]; for (int i = 0; i <arr....
  • 希尔排序算法源代码

    2012-01-19 11:15:06
    希尔排序的源代码; 平台:CentOS release 5.4 (Final) 编译器:GCC 4.3.2
  • 希尔排序代码

    2014-04-28 14:08:35
    希尔排序,C++实现,VS2010,完整工程文件,含注释
  • 这一篇我们说一下希尔排序,当然了如果学习希尔排序 那么就要知道插入排序的原理,因为希尔排序算的上是插入排序的进化版 如果没有学习过插入排序 那么就给一个传送门! ...学习了插入排序我们就可以对希尔排序进行讲解...
  • 直接插入排序 冒泡排序 快速排序 直接选择排序 堆排序 希尔排序
  • 希尔排序java代码

    2012-04-16 15:40:52
    希尔排序 希尔排序希尔排序希尔排序希尔排序希尔排序希尔排序希尔排序
  • 本文实现了八个常用的排序算法:插入排序、冒泡排序、选择排序、希尔排序 、快速排序、归并排序、堆排序和LST基数排序 首先是算法实现文件Sort.h,代码如下: /* * 实现了八个常用的排序算法:插入排序、冒泡排序...
  • 希尔排序图解与代码

    2021-08-12 22:08:57
    希尔排序(Shell Sort)是插入排序的一种算法,是对直接插入排序的一个优化,也称缩小增量排序。希尔排序是非稳定排序算法。 希尔排序因DL.Shell于1959年提出而得名。 算法思想 先用白话说描述,先排个大概近似的,...
  • 主要为大家详细介绍了Java经典排序算法之希尔排序,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
  • NULL 博文链接:https://wojiaolongyinong.iteye.com/blog/1867491
  • 希尔排序 算法原理:(希尔排序又称缩小增量排序。) 基本思想:先将原表按增量ht分组,每个子文件按照直接插入法排序。同样,用下一个增量ht/2将文件再分为子文件,再直接插入法排序。直到ht=1时整个文件排好序。 ...
  • 希尔排序(Shell) 思想:每次获取数组中最小的数放在最前面,共进行n-1轮 优缺点:好理解易实现,但是效率低下且不稳定 复杂度: 不需要额外的辅助空间,空间复杂度为O(1) 时间复杂度:O(n^2) 稳定性:不稳定 ...
  • 【希尔排序】C++实现希尔排序代码

    千次阅读 2018-08-16 10:42:22
    void shellSort(int a[], int n) //a -- 待排序的数组, n -- 数组的长度 { int i,j,gap; // gap为步长,每次减为原来的一半。 for (gap = n / 2; gap > 0; gap /= 2) { // 共gap个组,对每一组都执行直接插入...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 33,341
精华内容 13,336
关键字:

希尔排序完整代码