希尔排序(Shell Sort)是插入排序的一种。是针对直接插入排序算法的改进。该方法又称缩小增量排序,因DL.Shell于1959年提出而得名。
基本思想:
先取一个小于n的整数d1作为第一个增量,把文件的全部记录分组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序;然后,取第二个增量d2<d1重复上述的分组和排序,直至所取的增量dt=1(dt<dt-l<…<d2<d1),即所有记录放在同一组中进行直接插入排序为止。
操作方法:
选择一个增量序列t1,t2,…,tk,其中ti>tj,tk=1;
按增量序列个数k,对序列进行k 趟排序;
每趟排序,根据对应的增量ti,将待排序列分割成若干长度为m 的子序列,分别对各子表进行直接插入排序。仅增量因子为1 时,整个序列作为一个表来处理,表长度即为整个序列的长度。
希尔排序的示例:
示例2:
动画演示: http://www.tyut.edu.cn/kecheng1/site01/suanfayanshi/shell_sort.asp
算法实现:
我们简单处理增量序列:增量序列d = {n/2 ,n/4, n/8 .....1} n为要排序数的个数
即:先将要排序的一组记录按某个增量d(n/2,n为要排序数的个数)分成若干组子序列,每组中记录的下标相差d.对每组中全部元素进行直接插入排序,然后再用一个较小的增量(d/2)对它进行分组,在每组中再进行直接插入排序。继续不断缩小增量直至为1,最后使用直接插入排序完成排序。
Java代码:
public class ShellSort { public static void main(String[] args) { int[] a = {49, 38, 65, 97, 76, 13, 27, 49, 78, 34, 12, 64, 1}; System.out.println("排序之前:"); print(a); int d = a.length; while (d >= 1) { d = d / 2; if (d >0) { System.out.println("\nd=" + d); } for (int x = 0; x < d; x++) { //对分成的d组数据进行排序 for (int i = x + d; i < a.length; i = i + d) { //对某一组相差为d的数据进行比较 int temp = a[i]; //复制为哨兵,即待排序元素 int j; for (j = i - d; j >= 0 && a[j] > temp; j = j - d) { //寻找待插入位置, 如果当前数字大于待排序元素,则把当前数字后移d位 a[j + d] = a[j]; } a[j + d] = temp; //添加到正确位置 } System.out.println("第" + (x+1) + "组的结果:"); print(a); } } System.out.println(); System.out.println("排序之后:"); print(a); } private static void print(int[] a) { for (int i = 0; i < a.length; i++) { System.out.print(a[i] + " "); } System.out.println(); } }
结果:
排序之前: 49 38 65 97 76 13 27 49 78 34 12 64 1 d=6 第1组的结果: 1 38 65 97 76 13 27 49 78 34 12 64 49 第2组的结果: 1 38 65 97 76 13 27 49 78 34 12 64 49 第3组的结果: 1 38 65 97 76 13 27 49 78 34 12 64 49 第4组的结果: 1 38 65 34 76 13 27 49 78 97 12 64 49 第5组的结果: 1 38 65 34 12 13 27 49 78 97 76 64 49 第6组的结果: 1 38 65 34 12 13 27 49 78 97 76 64 49 d=3 第1组的结果: 1 38 65 27 12 13 34 49 78 49 76 64 97 第2组的结果: 1 12 65 27 38 13 34 49 78 49 76 64 97 第3组的结果: 1 12 13 27 38 64 34 49 65 49 76 78 97 d=1 第1组的结果: 1 12 13 27 34 38 49 49 64 65 76 78 97 排序之后: 1 12 13 27 34 38 49 49 64 65 76 78 97
稳定性:
由于多次插入排序,我们知道一次插入排序是稳定的,不会改变相同元素的相对顺序,但在不同的插入排序过程中,相同的元素可能在各自的插入排序中移动,最后其稳定性就会被打乱,所以shell排序是不稳定的。
相关推荐
详解Java常用排序算法-希尔排序
基于python的排序算法-希尔排序Shell Sort
算法-数据结构和算法-12-希尔排序.rar
经典排序算法 - 希尔排序Shell sort 经典排序算法 - 堆排序Heap sort序 经典排序算法 - 地精排序Gnome Sort 经典排序算法 - 奇偶排序Odd-even sort 经典排序算法 - 梳排序Comb sort 经典排序算法 - 耐心排序...
各类排序算法整理--C语言描述--本人编写 排序算法种类有: 冒泡 快速排序 堆排序 希尔排序 插入排序 选择排序 二路归并排序
实现以下常用的内部排序算法并进行性能比较:"直接插入排序"," 折半插入排序"," 2—路插入排序"," 表插入排序"," 希尔排序"," 起泡排序"," 快速排序"," 简单选择排序"," 树形选择排序"," 堆排序"," 归并排序"," 链式...
算法-理论基础- 排序- 希尔排序(包含源程序).rar
多线程实现排序算法的比较:希尔排序、快速排序、堆排序。用java语言实现,很经典,需要的可以下载看看!
此文件为数据结构中的九种排序算法,包含一些排序方法的过程,其九种排序包括:直接插入排序,折半插入排序,希尔排序,冒泡排序,快速排序,选择排序,堆排序,归并排序,基数排序!
Java代码-排序-直接插入排序、希尔排序、直接选择排序、冒泡排序、堆排序、快速排序、归并排序中部分排序以及算法-贪心法,大家可以将源码下载下来进行学习,附带着注释和解释,有不理解的可以找博主一起探讨,共同...
C#算法 -- (三)希尔排序 朋友们,我最近加紧写C#的一些算法。选择排序,插入算法是我已经推出的。现推出希尔排序.今后,如有时间我将依次推出其它的算法编写。 希尔排序是将组分段,进行插入排序. 对想提高C#语言编程...
七大排序算法如下: 交换排序:快速排序quicksort,冒泡排序bubblesort 选择排序:直接选择排序selectionsort,堆排序maxheapsort 插入排序:直接插入排序insertsort,希尔排序shellsort 合并排序:归并排序...
文档中包含了希尔排序的基本原理和实现方法,并提供了详细的代码示例和解析。 通过学习和完成这个练习,读者将能够掌握希尔排序算法的思想和实现过程,并了解其在排序算法中的应用。此外,文档还提供了练习题和答案...
各种排序算法,包括希尔算法,快速排序,堆排序-A variety of sorting algorithms, including the Hill algorithm, quick sort, heap sort
快速排序
有选择排序,冒泡排序,希尔排序,插入排序,归并排序算法
排序作为最基础的算法,有选择排序,冒泡排序,插入排序,希尔排序,堆排序,快速排序,归并排续等,我会用c++写一下,欢迎交流~
数据结构排序算法中的希尔(shell)排序,可供初学者参考
输入n个整数,分别用希尔排序、快速排序、堆排序和归并排序实现由小到大排序并输出排序结果。要求n=10,15,20进行三组排序实验...实验目的:掌握希尔排序、快速排序、堆排序、归并排序算法。 (zip中含代码及运行截图)
8.12-8.19_冒泡_选择_插入_希尔_快速_归并_基数_堆排序_排序算法Swift代码及UI演示