一.排序方法
- 先取一个小于n的整数increment作为第一个增量,把文件的全部记录分成increment个组。所有距离为increment的倍数的记录放在同一个组中。先在各组内进行直接插人排序。
- 取第二个增量increment(小于1中的increment)重复上述的分组和排序,直至所取的增量increment=1,即所有记录放在同一组中进行直接插入排序为止。
- 希尔排序实质上是一种分组插入方法。
二.动画演示
http://student.zjzk.cn/course_ware/data_structure/web/flashhtml/shell.htm
三.Java代码
public static int[] shellSort(int[] data) { int increment = data.length; // 区间为increment int temp = 0; while (true) { increment = increment / 2; // 分成了几组,一组一组处理 for (int x = 0; x < increment; x++) { // 下面就是直接插入排序,只是区间由1变成了increment for (int i = x + increment; i < data.length; i += increment) { if (data[i - increment] > data[i]) { temp = data[i]; int j = i - increment; for (; j >= 0 && data[j] > temp; j -= increment) { data[j + increment] = data[j]; } data[j + increment] = temp; } } } if (increment == 1) { break; } } return data; }
四. 时间复杂度和稳定性
- 希尔排序的时间复杂度到现在都还没有定论是多少,原因是因为希尔排序需要大量的数学知识做支撑。时间复杂度介于O (n log2n )-O( ns ) 1<s<2。 希尔排序时间复杂度最坏情况下为O(n2 ),其平均时间复杂度与每次选择的增量密切相关,但要优于直接插入排序。
- 希尔排序是不稳定的。
相关推荐
Java数据结构与算法学习笔记之排序 冒泡排序,选择排序,插入排序,希尔排序, 归并排序, 快速排序.
排序的基本概念以及其算法的种类,介绍几种常见的排序算法的算法:冒泡排序、选择排序、插入排序、归并排序、快速排序、希尔排序的算法和分析它们各自的复杂度,然后以表格的形式,清晰直观的表现出它们的复杂度的...
本资源包含《数据结构》考研的九种内部排序算法考点的算法代码及排序过程图示,以表格、图文方式详细讲解每一种排序算法的排序过程。 包含的九种内部排序有:直接插入排序、折半排序、希尔排序、冒泡排序、快速排序...
用flash方式演示各种数据结构基础算法3——排序部分,很直观,合适基础学习者使用。里面包括:堆排序.swf,规并排序.swf,基数排序.swf,快速排序.swf,冒泡排序.swf,桶式排序法.swf,希尔排序.swf,直接插入排序....
数据结构-3期(KC002) 希尔排序算法.docx 学习资料 复习资料 教学资源
Java数据结构和算法介绍了计算机编程中使用的数据结构和算法,对于在计算机应用中如何操作和管理数据以取得最优性能提供了深入浅出的讲解。全书共分为15章,分别讲述了基本概念、数组、简单排序、堆和队列、链表、...
希尔排序算法描述如下:将一个数据序列分成若干组,每组由若干相隔一段距离(称为增量)的元素组成,在一个组内采用直接插入排序算法进行排序; 增量初值通常为数据序列长度的一半,以后每趟增量减半,最后值为1....
Java数据结构和算法中文第二版(1) Java数据结构和算法中文第二版(2) 【内容简介】 本书可帮助读者: 通过由基于JAVA的演示所组成的可视专题讨论来掌握数据结构和算法 学会如何为常见和不太常见的编程条件选择...
希尔排序算法,对于学习数据结构的同学,这是一个好东西
算法/数据结构/Python/剑指offer/机器学习/leetcode 数据结构markdown格式 链表及常见操作 平衡查找树AVL 三种方法检测变位词Anagram 构建堆 二分查找 二叉查找树 二叉树 冒泡排序 英语单词拼写检查算法 ...
使用 python 实现十种最常见的排序算法:选择排序、冒泡排序、插入排序、归并排序、桶排序、计数排序、基数排序、(随机)快速排序、希尔排序和堆...适用于数据结构与算法的学习过程中,也是面试过程中常被问到的问题。
3 数据类型、运算符与表达式 3.1 C语言的数据类型 32 3.2 常量与变量 33 23.2.1 常量和符号常量 33 3.2.2 变量 33 3.3 整型数据 34 3.3.1 整型常量的表示方法 34 3.3.2 整型变量 35 3.4 实型数据 37 3.4.1 实型常量...
学习的大部分基础数据结构和相关的算法 实现语言主要是C/C++ BST: 二分搜索树 BubbleSort: 冒泡排序 CircleLinkList: 循环链表 Expression: 表达式求值 Fibonacci: 斐波那契数列 Floyd: 弗洛伊德算法 Graphic: 图...
枚举算法,递归与分治策略,递归与迭代的思想、求最大值最小值、线性查找、二分查找与冒泡排序以及选择与交换排序、插入和希尔排序。本课程除了强调经典的算法理论和模型,亦兼顾编程实践能力。力图使得学员面对复杂...
光盘内容可在DOS环境下运行的以类C语言描述的“数据结构算法动态模拟辅助教学软件,以及在Windows环境下运行的以类PASCAL或类C两种语言描述的“数据结构算法动态模拟辅助教学软件”。 本书可作为计算机类专业或信息...
通过由基于JAVA的演示所组成的可视专题讨论来掌握数据结构和算法 学会如何为常见和不太常见的编程条件选择正确的算法 利用数据结构和算法为现实世界的处理过程建模 了解不同的数据结构的优势和弱点,考虑如何利用...
本项目涵盖了数据结构中的七个重要的排序算法,选择,插入,冒泡,归并,希尔,快速和堆排序,可实现任何的List类型和数组类型,进行排序,除String类型外都可以进行排序,为使用开发者和学习者使用这七种经典算法...
数据结构和算法能起到什么作用? 数据结构的概述 算法的概述 一些定义 面向对象编程 软件工程 对于C++程序员的Java Java数据结构的类库 小结 问题 第2章 数组 Array专题Applet Java中数组的基础知识 将程序划分成类...
排序算法是《数据结构与算法》中最基本的算法之一。 排序算法可以分为内部排序和外部排序。 内部排序是数据记录在内存中进行排序。 而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要...