搜文章
推荐 原创 视频 Java开发 iOS开发 前端开发 JavaScript开发 Android开发 PHP开发 数据库 开发工具 Python开发 Kotlin开发 Ruby开发 .NET开发 服务器运维 开放平台 架构师 大数据 云计算 人工智能 开发语言 其它开发
Lambda在线 > 药菌 > 希尔排序学习笔记

希尔排序学习笔记

药菌 2018-10-29

1.原理介绍

简单插入排序算法的本质是比较和交换,数据序列越接近有序,比较次数就越小。而序列中的逆序个数决定交换的次数。因此,可以通过分组来改进简单插入排序的复杂度。

希尔排序(Shell's Sort)便是插入排序的一种又称“缩小增量排序”(Diminishing Increment Sort),是直接插入排序算法的一种更高效的改进版本。该方法因D.L.Shell于1959年提出而著名。希尔排序是非稳定排序算法。

基本思想:分割成若干个较小的子文件,对各别进行直接插入排序,当文件达到基本有时再对整个文件进行一次直接插入排序。 对待排记录序列先作“宏观”调整,再作“微观”调整。 “宏观”调整指的是“跳跃式”的插入排序。

排序过程示例如下:

2.希尔排序特点

1. 子序列的构成不是简单“逐段分割”,而将相隔某个增量记录组一个子序列
2. 希尔排序可提高速度,因为
  • 分组后 n值减小, n² 更小,而 T(n)=O(n²), 所以 T(n)从总体上看是减小了

  • 关键字较小的记录跳跃式前移,在进行最后一趟增量为 1的插入排序时, 序
    列已基本有序

3. 增量序列取法
  • 无除 1以外的公因子

  • 最后一个增量值必须为 1

3.代码实现

1#include <iostream>
2
3using namespace std;
4
5//输出函数
6template <class T>
7void printArr(T *arrint length)
8{

9    for (int i = 0; i < length; ++i)
10    {
11        cout << arr[i] << " ";
12    }
13    cout << endl;
14}
15
16
17//希尔排序
18void shellsort(int arr[], int n)
19
{
20    int gap = n;
21    do 
22    {
23        gap = gap / 3 + 1;//增量序列
24        //依次对gap个子序列进行排序
25        for (int i = 0; i< gap; i++)
26        {
27            cout << "第" << i << "个子序列排序前:" ;
28            //对每个子序列进行简单插入排序
29            for (int j = i; j < n; j = j + gap)
30            {
31                cout << arr[j] << " ";
32            }
33            cout << endl;
34
35            //对每个子序列进行简单插入排序
36           for (int j = i + gap; j<n; j=j+gap)
37           {
38
39               if (arr[j] < arr[j-gap])
40               {
41                   //防止覆盖,使用哨兵保留
42                   int temp = arr[j];
43                   int k = j - gap;
44                   while (temp < arr[k] && k>=0)
45                   {
46                       //当前元素向后拷贝移动
47                       arr[k + gap] = arr[k];
48                       k = k - gap;
49                   }
50                   //空出位置插入待排序元素
51                   arr[k + gap] = temp;
52               }
53           }
54
55           cout << "第" << i << "个子序列排序后:";
56           for (int j = i; j < n; j = j + gap)
57           {
58               cout << arr[j] << " ";
59           }
60           cout << endl;
61
62        }
63        cout << "间隔为:" << gap << "时排序结果:" << endl;
64        printArr(arr, 10);
65        cout << endl;
66
67    } while (gap > 1);
68}
69
70int main()
71
{
72    int a[] = { 1123243539010087};
73
74    cout << "排序前:" << endl;
75    printArr(a, 10);
76    cout << endl;
77    shellsort(a, 10);
78
79    cout << "排序后:" << endl;
80    printArr(a, 10);
81
82    system("pause");
83    return 0;
84}

程序运行结果如下:



版权声明:本站内容全部来自于腾讯微信公众号,属第三方自助推荐收录。《希尔排序学习笔记》的版权归原作者「药菌」所有,文章言论观点不代表Lambda在线的观点, Lambda在线不承担任何法律责任。如需删除可联系QQ:516101458

文章来源: 阅读原文

相关阅读

关注药菌微信公众号

药菌微信公众号:ayjgzh

药菌

手机扫描上方二维码即可关注药菌微信公众号

药菌最新文章

精品公众号随机推荐