[数据结构] 希尔排序

概述

  希尔排序法(缩小增量法) 属于插入类排序,是将整个无序列分割成若干小的子序列分别进行插入排序的方法。

  把记录按下标的一定增量分组,对每组使用直接插入排序算法排序;随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个文件恰被分成一组,算法便终止。

希尔排序是基于插入排序的以下两点性质而提出改进方法的:

  • 插入排序在对几乎已经排好序的数据操作时,效率高,即可以达到线性排序的效率。
  • 但插入排序一般来说是低效的,因为插入排序每次只能将数据移动一位。

实现过程

  先取一个正整数d1小于n,把所有序号相隔d1的数组元素放一组,组内进行直接插入排序;然后取d2小于d1,重复上述分组和排序操作;直至di=1,即所有记录放进一个组中排序为止。

  例如,假设有这样一组数[ 13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10 ],如果我们以步长为5开始进行排序,我们可以通过将这列表放在有5列的表中来更好地描述算法,这样他们就应该看起来是这样:

13 14 94 33 82 
25 59 94 65 23 
45 27 73 25 39 
10

然后我们对每列进行排序:

10 14 73 25 23 
13 27 94 33 39 
25 59 94 65 82 
45

  将上述四行数字,依序接在一起时我们得到:[ 10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45 ].这时10已经移至正确位置了,然后再以3为步长进行排序:

10 14 73 
25 23 13 
27 94 33 
39 25 59 
94 65 82 
45

排序之后变为:

10 14 13 
25 23 33 
27 25 59 
39 65 73 
45 94 82 
94

最后以1步长进行排序(此时就是简单的插入排序了)。

实现效率

  希尔排序是一个不稳定的排序,其时间复杂度受步长(增量)的影响。

  空间复杂度: O(1)

  时间复杂度: 平均 O(n^1.3) 
最好 O(n) 
最坏 O(n^2)

Java实现

public static void shellSort(int[] a) {
        int gap = 1, i, j, len = a.length;
        int temp;//插入排序交换值的暂存
        //确定初始步长
        while (gap < len / 3){
            gap = gap * 3 + 1;
        }
        for (; gap > 0; gap /= 3){//循环遍历步长,最后必为1
            for (i = gap; i < len; i++) {//每一列依次向前做插入排序
                temp = a[i];
                //每一列中在a[i]上面且比a[i]大的元素依次向下移动
                for (j = i - gap; j >= 0 && a[j] > temp; j -= gap){
                    a[j + gap] = a[j];
                }
                //a[i]填补空白,完成一列中的依次插入排序
                a[j + gap] = temp;
            }
        }
    }

版权声明:请尊重个人劳动成果,转载注明出处,谢谢!

http://blog.csdn.net/amazing7/article/details/51386145

时间: 2024-05-25 18:45:16

[数据结构] 希尔排序的相关文章

数据结构例程——插入排序之希尔排序

本文是[数据结构基础系列(9):排序]中第3课时[插入排序之希尔排序]的例程. 1.希尔排序 #include <stdio.h> #define MaxSize 20 typedef int KeyType; //定义关键字类型 typedef char InfoType[10]; typedef struct //记录类型 { KeyType key; //关键字项 InfoType data; //其他数据项,类型为InfoType } RecType; //排序的记录类型定义 void

数据结构和算法12 之希尔排序

 上一章我们学习了冒泡排序.选择排序和插入排序三种基础排序算法,这三种排序算法比较简单,时间复杂度均为O(N2),效率不高.这节我们讨论一个高级排序算法:希尔排序.希尔排序是基于插入排序的,插入排序有个弊端,假设一个很小的数据项在很靠近右端的位置上,那么所有的中间数据项都必须向右移动一位,这个步骤对每一个数据项都执行了将近N次的复制,这也是插入排序效率为O(N2)的原因.         希尔排序的中心思想是将数据进行分组,然后对每一组数据进行插入排序,在每一组数据都有序后,再对所有的分组利用插

数据结构内部排序实验报告

问题描述 数据结构内部排序实验报告 一.实验目的 1.掌握排序的有关概念和特点. 2.熟练掌握直接插入排序.希尔排序.冒泡排序.快速排序.简单选择排序.堆排序.归并排序.基数排序等算法的基本思想.. 3.关键字序列有序与无序,对于不同的排序方法有不同的影响,通过该实验进一步加深理解. 二.实验内容 设有关键字序列k={ 12 , 45 , 21 , 12 , 30 , 2 , 68 , 33 },试用各种排序算法进行排序. 三.实验环境 TC或VC++ 四.实验步骤 1.从键盘输入上述8个整数,

必须掌握的八种排序(1-2)--插入排序,希尔排序

很多人算法和数据结构不好,归根结底就是基础不扎实,算法和数据结构不好的话,达到的高度肯定不会很高,最近重新加强了一下自己的算法基础,决定从最基础的内容开始,如有不足的地方,欢迎指正. 排序方法可以分为五种∶插入排序.选择排序.交换排序.分配排序和归并排序. 在排序过程中,全部记录存放在内存,则称为内排序,如果排序过程中需要使用外存,则称为外排序. 首先来看一下八种排序之间的关系图 1. 直接插入排序 (1)基本思想:在要排序的一组数中,假设前面(n-1) [n>=2] 个数已经是排 好顺序的,现

python实现的希尔排序算法实例

  本文实例讲述了python实现希尔排序算法的方法.分享给大家供大家参考.具体如下: ? 1 2 3 4 5 6 7 8 9 10 11 12 13 14 def shellSort(items): inc = len(items) / 2 while inc: for i in xrange(len(items)): j = i temp = items[i] while j >= inc and items[j-inc] > temp: items[j] = items[j - inc]

C#算法----(三)希尔排序 (solarsoft原创)

朋友们,我最近加紧写C#的一些算法.选择排序,插入算法是我已经推出的.现推出希尔排序.今后,如有时间我将依次推出其它的算法编写.希尔排序是将组分段,进行插入排序.对想提高C#语言编程能力的朋友,我们可以互相探讨一下.如:下面的程序,并没有实现多态,来,帮它实现一下.using System;public class ShellSorter{  public void Sort(int [] list)  {      int inc;      for(inc=1;inc<=list.Lengt

C#的四种排序算法:冒泡排序、选择排序、插入排序和希尔排序

插入|排序|算法 本文介绍了C#的四种排序算法:冒泡排序.选择排序.插入排序和希尔排序 冒泡排序 using System: namespace BubbleSorter { public class BubbleSorter { public void Sort(int [] list) { int i,j,temp: bool done=false: j=1: while((j<list.Length)&&(!done)) { done=true: for(i=0:i<li

内部排序:插入排序和希尔排序的N种实现

前言 本来想将所有的内部排序总结为一篇博文,但是随着研究的深入,还是放弃了这个念头,斟前酌后,还是觉得分开来写比较好,具体原因,看完本篇博文也就自然明了了. 本篇文章主要探讨插入排序和希尔排序,之所将二者放在一起,很明显,是因为希尔排序是建立在插入排序的基础之上的. 注:以下各排序算法的N种实现方法大部分都是我根据算法思想,自己写出来的,或者是参考其本身的经典实现,我自己都已测试通过,但不敢保证一定都没问题,如果有疑问,欢迎指出. 插入排序 插入排序的思想很简单,它的基本操作就是将一个数据插入到

java中实现希尔排序算法

package Utils.Sort; /**   *希尔排序,要求待排序的数组必须实现Comparable接口   */   public class ShellSort implements SortStrategy   {   private int[] increment; /**   *利用希尔排序算法对数组obj进行排序   */   public void sort(Comparable[] obj)   {   if (obj == null)   {   throw new N