希尔排序的算法代码

希尔排序的时间复杂度为O(n*log2n) 空间复杂度为O（1）是一种不稳定的排序算法

思想：希尔排序也是一种插入排序方法,实际上是一种分组插入方法。先取定一个小于n的整数d1作为第一个增量,把表的全部记录分成d1个组,所有距离为d1的倍数的记录放在同一个组中,在各组内进行直接插入排序；然后,取第二个增量d2(＜d1),重复上述的分组和排序,直至所取的增量dt=1(dt<dt-1<…<d2<d1),即所有记录放在同一组中进行直接插入排序为止。

代码如下:

void ShellSort(int* data ,int length)
{
    if( data == NULL || length <= 0 )
        return;

int d = length/2;  //步长
    while( d )
    {
        for(int i = 0 ; i < d ; ++i) //根据步长分成组，对每组进行插入排序
        {
            //插入排序
            for(int j = i+d; j <length ; j +=d )
            {
                if( data[j] < data[j -d])
                {
                    int temp = data[j]; //哨兵
                    int k = j-d;
                    for(; k >=0&& temp < data[k]; k -=d)
                    {
                        data[k+d] =data[k];
                    }
                    data[k+d] =temp;
                }
            }
        }
        d = d/2;
    }
}

赞 (0)

相关推荐

  • C++实现八个常用的排序算法：插入排序、冒泡排序、选择排序、希尔排序等

    C++实现八个常用的排序算法：插入排序、冒泡排序、选择排序、希尔排序等

    本文实现了八个常用的排序算法:插入排序.冒泡排序.选择排序.希尔排序 .快速排序.归并排序.堆排序和LST基数排序 首先是算法实现文件Sort.h,代码如下: /* * 实现了八个常用的排序算法:插入排序.冒泡排序.选择排序.希尔排序 * 以及快速排序.归并排序.堆排序和LST基数排序 * @author gkh178 */ #include <iostream> template<class T> void swap_value(T &a, T &b) { T t

  • C++实现简单的希尔排序Shell Sort实例

    本文以实例形式讲述了基于C++实现简单的希尔排序Shell Sort的方法,是一个很经典的算法,具体实现代码如下: #include <iostream> using namespace std; void ShellSort(int* iArray,int length) { //初始化jump等于length int jump = length; //标记本趟检测是否进行了交换, // 若进行了 则还有下次从头开始的检测, // 否则停止,继续改变jump的值 做另一趟排序 bool is

  • C++选择排序算法实例

    选择排序 选择排序是一种简单直观的排序算法,它的工作原理如下.首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾.以此类推,直到所有元素均排序完毕. 选择排序的主要优点与数据移动有关.如果某个元素位于正确的最终位置上,则它不会被移动.选择排序每次交换一对元素,它们当中至少有一个将被移到其最终位置上,因此对n个元素的表进行排序总共进行至多n-1次交换.在所有的完全依靠交换去移动元素的排序方法中,选择排序属于非常

  • C++归并排序算法实例

    归并排序 归并排序算法是采用分治法的一个非常典型的应用.归并排序的思想是将一个数组中的数都分成单个的:对于单独的一个数,它肯定是有序的,然后,我们将这些有序的单个数在合并起来,组成一个有序的数列.这就是归并排序的思想.它的时间复杂度为O(N*logN). 代码实现 复制代码 代码如下: #include <iostream> using namespace std;   //将有二个有序数列a[first...mid]和a[mid...last]合并. void mergearray(int

  • c++几种基本的插入排序(图文)

    c++几种基本的插入排序(图文)

    1.插入排序 插入排序(Insertion Sort)是一种简单直观的排序算法.它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入.插入排序在实现上,通常采用in-place排序(即只需用到O(1)的额外空间的排序),因而在从后向前扫描过程中,需要反复把已排序元素逐步向后挪位,为最新元素提供插入空间. 时间复杂度:O(n^2); 算法描述: 1.从第一个元素开始,该元素可以认为已经被排序 2.取出下一个元素,在已经排序的元素序列中从后向前扫描 3.如果

  • C/C++实现快速排序的方法

    快速排序不会直接得到最终结果,只会把比k大和比k小的数分到k的两边.(你可以想象一下i和j是两个机器人,数据就是大小不一的石头,先取走i前面的石头留出回旋的空间,然后他们轮流分别挑选比k大和比k小的石头扔给对面,最后在他们中间把取走的那块石头放回去,于是比这块石头大的全扔给了j那一边,小的全扔给了i那一边.只是这次运气好,扔完一次刚好排整齐.)为了得到最后结果,需要再次对下标2两边的数组分别执行此步骤,然后再分解数组,直到数组不能再分解为止(只有一个数据),才能得到正确结果. -- 取自百度百科

  • C++插入排序算法实例

    插入排序 没事喜欢看看数据结构和算法,增加自己对数据结构和算法的认识,同时也增加自己的编程基本功.插入排序是排序中比较常见的一种,理解起来非常简单.现在比如有以下数据需要进行排序: 10 3 8 0 6 9 2 当使用插入排序进行升序排序时,排序的步骤是这样的: 10 3 8 0 6 9 2 // 取元素3,去和10进行对比 3 10 8 0 6 9 2 // 由于10比3大,将10向后移动,将3放置在原来10的位置:再取8与前一个元素10进行对比 3 8 10 0 6 9 2 // 同理移动1

  • C++冒泡排序算法实例

    冒泡排序 大学学习数据结构与算法最开始的时候,就讲了冒泡排序:可见这个排序算法是多么的经典.冒泡排序是一种非常简单的排序算法,它重复地走访过要排序的数列,每一次比较两个数,按照升序或降序的规则,对比较的两个数进行交换.比如现在我要对以下数据进行排序: 10 3 8 0 6 9 2 当使用冒泡排序进行升序排序时,排序的步骤是这样的: 3 10 8 0 6 9 2  // 10和3进行对比,10>3,交换位置 3 8 10 0 6 9 2  // 10再和8进行对比,10>8,交换位置 3 8 0

  • C++堆排序算法的实现方法

    C++堆排序算法的实现方法

    本文实例讲述了C++实现堆排序算法的方法,相信对于大家学习数据结构与算法会起到一定的帮助作用.具体内容如下: 首先,由于堆排序算法说起来比较长,所以在这里单独讲一下.堆排序是一种树形选择排序方法,它的特点是:在排序过程中,将L[n]看成是一棵完全二叉树的顺序存储结构,利用完全二叉树中双亲节点和孩子节点之间的内在关系,在当前无序区中选择关键字最大(或最小)的元素. 一.堆的定义 堆的定义如下:n个关键字序列L[n]成为堆,当且仅当该序列满足: ①L(i) <= L(2i)且L(i) <= L(2

  • 希尔排序的算法代码

    希尔排序的时间复杂度为O(n*log2n) 空间复杂度为O(1)是一种不稳定的排序算法 思想:希尔排序也是一种插入排序方法,实际上是一种分组插入方法.先取定一个小于n的整数d1作为第一个增量,把表的全部记录分成d1个组,所有距离为d1的倍数的记录放在同一个组中,在各组内进行直接插入排序:然后,取第二个增量d2(<d1),重复上述的分组和排序,直至所取的增量dt=1(dt<dt-1<-<d2<d1),即所有记录放在同一组中进行直接插入排序为止. 复制代码 代码如下: void

  • 浅析java 希尔排序(Shell)算法

    浅析java 希尔排序(Shell)算法

    先取一个小于n的整数d1作为第一个增量,把文件的全部记录分成d1个组.所有距离为dl的倍数的记录放在同一个组中.先在各组内进行直接插入排序:然后,取第二个增量d2<d1重复上述的分组和排序,直至所取的增量dt=1(dt<dt-l<:-<d2<d1),即所有记录放在同一组中进行直接插入排序为止. 该方法实质上是一种分组插入方法. 原理图: 源代码 复制代码 代码如下: package com.zc.manythread; /**  *  * @author 偶my耶  *  *

  • Java实现几种常见排序算法代码

    稳定度(稳定性)一个排序算法是稳定的,就是当有两个相等记录的关键字R和S,且在原本的列表中R出现在S之前,在排序过的列表中R也将会是在S之前. 排序算法分类 常见的有插入(插入排序/希尔排序).交换(冒泡排序/快速排序).选择(选择排序).合并(归并排序)等. 一.插入排序 插入排序(Insertion Sort),它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入.插入排序在实现上,通常采用in-place排序(即只需用到O(1)的额外空间的排序),

  • C++ 算法之希尔排序详解及实例

    C++ 算法之希尔排序详解及实例

    C++ 算法之希尔排序算法详解及实例 希尔排序算法 定义: 希尔排序是插入排序的一种,也称缩小增量排序,是直接插入排序算法的一种更高效的改进版本. 算法思想: 希尔排序是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序,随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个文件恰好被分为一组,算法终止. 时间复杂度: O(N) 空间复杂度: O(1) 性能: 希尔排序为不稳定算法(一次插入排序是稳定的,不会改变相同元素的相对顺序,但是在不同的插入排序中,相同的元素可能在各自的

  • C++实现希尔排序（ShellSort）

    本文实例为大家分享了C++实现希尔排序的具体代码,供大家参考,具体内容如下 一.思路: 希尔排序:又称缩小增量排序,是一种改进的插入排序算法,是不稳定的. 设排序元素序列有n个元素,首先取一个整数gap<n作为间隔,将全部元素分为gap个子序列,所有距离为gap的元素放在同一个子序列中,在每一个子序列中分别施行直接插入排序.然后缩小间隔gap,重复上述的子序列和排序工作. 二.实现程序: #include <iostream> using namespace std; const int

  • Java数据结构之插入排序与希尔排序

    目录 一.正文 1.排序的概念及其运用 1.1排序的概念 1.2排序运用 1.3常见的排序算法 2.插入排序算法的实现 2.1插入排序 二.测试代码 三.结语 一.正文 1.排序的概念及其运用 1.1排序的概念 排序:所谓排序,就是使一串记录,按照其中的某个或某些关键字的大小,递增或递减的排列起来的操作. 稳定性:假定在待排序的记录序列中,存在多个具有相同的关键字的记录,若经过排序,这些记录的相对次 序保持不变,即在原序列中,r[i]=r[j],且r[i]在r[j]之前,而在排序后的序列中,r[

  • C#实现希尔排序

    C#实现希尔排序

    对于大规模乱序的数组,插入排序很慢,因为它只会交换相邻的元素,因此元素只能一点一点地从数组地一段移动到另一端.希尔排序改进了插入排序,交换不相邻地元素以对数组地局部进行排序,最终用插入排序将局部有序的数组排序. 希尔排序的思想是使数组中任意间隔为 h 的元素都是有序的.这样的数组成为 h 有序数组.换句话说,一个 h 有序数组就是 h 个相互独立的有序数组组合在一起的一个数组. 在进行排序时,刚开始 h 很大,就能将元素移动到很远的地方,为实现更小的 h 有序创造方便.h 递减到 1 时,相当于

  • 细致解读希尔排序算法与相关的Java代码实现

    希尔排序(Shell's sort)是一种非常"神奇"的排序算法.说它"神奇",是因为没有任何人能清楚地说明它的性能到底能到什么情况.希尔排序因DL．Shell于1959年提出而得名.自从C. A. R. Hoare在1962年提出快速排序后,由于其更为简单,一般采用快速排序.但是,不少数学家们还是孜孜不倦地寻找希尔排序的最佳复杂度.作为普通程序员,我们可以学习下希尔的思路. 顺便说一句,在希尔排序出现之前,计算机界普遍存在"排序算法不可能突破O(n2)&

  • java 算法之希尔排序详解及实现代码

    java 算法之希尔排序 一.思想 希尔排序:使数组中任意间隔为h的元素都是有序的.在进行排序的时候,如果h很大,我们就能将元素移动到很远的地方,为实现更小的h有序创造方便.用这种方式,对任意以1结尾的h序列,我们都能够将数据排序: 二.概念 h有序数组:任意间隔为h的元素都是有序的数组: 三.高效原因 对于大规模乱序数组插入排序很慢,因为它只会交换相邻的元素,因此元素只能一点一点地从数组的一端移动到另一段:   希尔排序更高效的原因:它权衡了子数组的规模和有序性,在排序之初,各个子数组都很短:

  • Swift编程中实现希尔排序算法的代码实例

    Swift编程中实现希尔排序算法的代码实例

    思想 希尔排序的实质就是分组插入排序,该方法又称缩小增量排序,因DL．Shell于1959年提出而得名. 该方法的基本思想是:先将整个待排元素序列分割成若干个子序列(由相隔某个"增量"的元素组成的)分别进行直接插入排序,然后依次缩减增量再进行排序,待整个序列中的元素基本有序(增量足够小)时,再对全体元素进行一次直接插入排序.因为直接插入排序在元素基本有序的情况下(接近最好情况),效率是很高的,因此希尔排序在时间效率上比前两种方法有较大提高. 以n=10的一个数组49, 38, 65,

随机推荐