希尔排序(shell‘ sort)

希尔排序是1959 年由D.L.Shell 提出来的,相对直接排序有较大的改进。希尔排序又叫缩小增量排序

基本思想:

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

操作方法:

  1. 选择一个增量序列t1,t2,…,tk,其中ti>tj,tk=1;
  2. 按增量序列个数k,对序列进行k 趟排序;
  3. 每趟排序,根据对应的增量ti,将待排序列分割成若干长度为m 的子序列,分别对各子表进行直接插入排序。仅增量因子为1 时,整个序列作为一个表来处理,表长度即为整个序列的长度。

希尔排序的示例:

算法实现:

01.void print(int a[], int n ,int i){  
02.    cout<<i <<":";  
03.    for(int j= 0; j<8; j++){  
04.        cout<<a[j] <<" ";  
05.    }  
06.    cout<<endl;  
07.}  
08./** 
09. * 直接插入排序的一般形式 
10. * 
11. * @param int dk 缩小增量,如果是直接插入排序,dk=1 
12. * 
13. */  
14.  
15.void ShellInsertSort(int a[], int n, int dk)  //直接排序
16.{  
17.    for(int i= dk; i<n; ++i){  
18.        if(a[i] < a[i-dk]){          //若第i个元素大于i-1元素,直接插入。小于的话,移动有序表后插入  
19.            int j = i-dk;     
20.            int x = a[i];           //复制为哨兵,即存储待排序元素  
21.            a[i] = a[i-dk];         //首先后移一个元素  
22.            while(x < a[j]){     //查找在有序表的插入位置  
23.                a[j+dk] = a[j];  
24.                j -= dk;             //元素后移  
25.            }  
26.            a[j+dk] = x;            //插入到正确位置  
27.        }  
28.        print(a, n,i );  
29.    }  
30.      
31.}  
32.  
33./** 
34. * 先按增量d(n/2,n为要排序数的个数进行希尔排序 
35. * 
36. */  
37.void shellSort(int a[], int n)//希尔排序
   {  
38.  
39.    int dk = n/2;  
40.    while( dk >= 1  ){  
41.        ShellInsertSort(a, n, dk);  
42.        dk = dk/2;  
43.    }  
44.}  
45.int main(){  
46.    int a[8] = {3,1,5,7,2,4,9,6};  
47.    //ShellInsertSort(a,8,1); //直接插入排序  
48.    shellSort(a,8);           //希尔插入排序  
49.    print(a,8,8);  
50.}  

单处理增量序列:增量序列d = {n/2 ,n/4, n/8 .....1} n为要排序数的个数

即:先将要排序的一组记录按某个增量d(n/2,n为要排序数的个数)分成若干组子序列,每组中记录的下标相差d.对每组中全部元素进行直接插入排序,然后再用一个较小的增量(d/2)对它进行分组,在每组中再进行直接插入排序。继续不断缩小增量直至为1,最后使用直接插入排序完成排序。

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏海天一树

图的深度优先搜索

图有两种最基本的搜索算法,一种是深度优先搜索,另一种是广度优先搜索。本节先介绍深度优先搜索。

972
来自专栏ACM算法日常

分割排序(排序)- HDU 1106

输入一行数字,如果我们把这行数字中的‘5’都看成空格,那么就得到一行用空格分割的若干非负整数(可能有些整数以‘0’开头,这些头部的‘0’应该被忽略掉,除非这个整...

781
来自专栏Java爬坑系列

【JAVA零基础入门系列】Day10 Java中的数组

  什么是数组?顾名思义,就是数据的组合,把一些相同类型的数放到一组里去。   那为什么要用数组呢?比如需要统计全班同学的成绩的时候,如果给班上50个同学的成绩...

2116
来自专栏智能算法

Python学习(四)---- 列表生成式、生成器、迭代器和内置函数

https://blog.csdn.net/fgf00/article/details/52061971

972
来自专栏从零开始学 Web 前端

05 - JavaSE之数组

1634
来自专栏老司机的技术博客

人人都能学会的python编程教程6:列表(list)

当索引超出了范围时,Python会报一个IndexError错误,所以,要确保索引不要越界,记得最后一个元素的索引是len(classmates) - 1。如果...

43110
来自专栏运维技术迷

PHP-数组排序

分别定义一个数值数组和一个关联数组. $age=array("lili"=&gt;"23","bob"=&gt;"30","ben"=&gt;"44"); $c...

3196
来自专栏武培轩的专栏

排序算法-插入排序

算法简介 插入排序(Insertion Sort)是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应...

2764
来自专栏desperate633

Python爬虫之正则表达式入门正则表达式语法正则表达式实例ReMatch对象贪婪匹配和最小匹配

Re库是Python的标准库,主要用于字符串匹配 调用方式: import re

751
来自专栏从流域到海域

《笨办法学Python》 第4课手记

《笨办法学Python》 第4课手记 这节课目的是让你掌握变量,跟C语言非常类似,很简单。 左边是变量名用”=”号给变量赋值。 不同的是我没有看到变量声明,作者...

1898

扫码关注云+社区

领取腾讯云代金券