希尔排序

1、希尔排序介绍

希尔排序是对直接插入排序算法的一种改进,当记录较少或者记录本身基本有序的时候直接插入排序的优势非常明显,所以希尔排序就是通过人为的创造这两个条件,然后进行插入排序,基本思想是设置一个增量increment,然后将原始记录“看成”increment组数据,并对每组数据进行直接插入排序,然后increment不断的缩小,直到为1的时候,就看成对一组数据的插入排序了。

引用一个别人的博文的例子“经典排序算法 - 希尔排序Shell sort ” 

准备待排数组[6 2 4 1 5 9]

首先需要选取关键字,例如关键是3和1(第一步分成三组,第二步分成一组),那么待排数组分成了以下三个虚拟组:

[6 1]一组

[2 5]二组

[4 9]三组

看仔细啊,不是临近的两个数字分组,而是3(分成了三组)的倍数的数字分成了一组,

就是每隔3个数取一个,每隔三个再取一个,这样取出来的数字放到一组,

把它们当成一组,但不实际分组,只是当成一组来看,所以上边的"组"实际上并不存在,只是为了说明分组关系

对以上三组分别进行插入排序变成下边这样

[1 6] [2 5] [4 9]

具体过程:

[6 1]6和1交换变成[1 6]

[2 5]2与5不动还是[2 5]

[4 9]4与9不动还是[4 9]

第一趟排序状态演示:

待排数组:[6 2 4 1 5 9]

排后数组:[1 2 4 6 5 9]

第二趟关键字取的是1,即每隔一个取一个组成新数组,实际上就是只有一组啦,隔一取一就全部取出来了嘛

此时待排数组为:[1 2 4 6 5 9]

直接对它进行插入排序

[1 2 4]都不用动,过程省略,到5的时候,将5取出,在前边的有序数组里找到适合它的位置插入,就是4后边,6前边

后边的也不用改,所以排序完毕

顺序输出结果:[1 2 4 5 6 9]

2、希尔排序的关键是如何取关键字,因为其它内容与插入排序一样

好的增量序列的共同特征:

① 最后一个增量必须为1

② 应该尽量避免序列中的值(尤其是相邻的值)互为倍数的情况

参见 http://baike.baidu.com/view/2217047.htm

大量的研究表明,当增量序列为dlta[k]=2^(t-k+1)-1      (t、k有一定的范围)的时候可以获得不错的效果公式参见大话数据结构p395

下面为C++的shell排序实现:

// 希尔排序.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include<iostream>
using namespace std;
//输入数组的名字和长度,然后用希尔排序方法进行排序
void shell_sort(int *p,int n)
{
    int i,j;
    int increment=n;
    while(increment>1)
    {
        increment=increment/3+1;//增量的选取
        for( i=increment;i<n;i++ )
        {
            if(p[i]<p[i-increment])
            {
                int temp=p[i];//创建一个临时变量存放p[i],免得到后面找位置的时候被覆盖掉
                //像插入排序一样组内数据不断后移,寻找合适的插入位置
                for( j=i-increment;j>=0&&p[j]>temp;j=j-increment)
                {
                    p[j+increment]=p[j];
                }
                //插入数据
                p[j+increment]=temp;
            }
        }
    }
}
int _tmain(int argc, _TCHAR* argv[])
{
    int a[10]={3,9,1,5,8,3,7,4,6,2};
    shell_sort(a,10);
    for(int i=0;i<10;i++)
    {
        cout<<a[i]<<' ';
    }
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏C语言及其他语言

[每日一题]统计字符

这也是一道字符串类型中比较常规的题(但含自定义函数哦),但前提得知道一个函数哦,就会简单很多!!! 如果你不知道,写完这题你就知道了哦!!! 题目描述 编写一...

3678
来自专栏彭湖湾的编程世界

【算法】哈希表的诞生

参考资料 《算法(java)》                           — — Robert Sedgewick, Kevin Wayne 《数据结...

35410
来自专栏大数据杂谈

从 Zero 到 Hero ,一文掌握 Python

2109
来自专栏牛客网

校招面试手撕算法汇总

所有题目都是从面经中提取而来,持续更新。 本人也是菜鸟一枚,帖子也会相应的发布自己对于题目的解法和看法,但是可能想得不够,也希望大家能够一起讨论,一起进步。 1...

41211
来自专栏诸葛青云的专栏

C语言for语句用法详解

在C语言中,for语句使用最为灵活,它完全可以取代 while 语句。它的一般形式为:

830
来自专栏彭湖湾的编程世界

【算法】哈希表的诞生

《算法(java)》                           — — Robert Sedgewick, Kevin Wayne

1567
来自专栏小狼的世界

两个有序数组中查找第K大数

题目:两个数组A、B,长度分别为m、n,即A(m)、B(n),分别是递增数组。求第K大的数字。

2322
来自专栏blackheart的专栏

[程序设计语言]-[核心概念]-03:控制流

0.概述 前面介绍了语言的演进以及一些基础概念后,从本篇开始进入了语言的核心问题中。这一篇讨论的是语言计算模型(大致可以用控制流来表述),大致如下7种: 顺序执...

21310
来自专栏chenjx85的技术专栏

leetcode-551-Student Attendance Record I(判断是否出现连续几个相同字符)

1466
来自专栏决胜机器学习

有趣的算法(七) ——快速排序改进算法

有趣的算法(七) ——快速排序改进算法 (原创内容,转载请注明来源,谢谢) 一、概述 快速排序,被认为是最好的排序算法之一。快速排序是20世纪60年代被提出...

3304

扫码关注云+社区

领取腾讯云代金券