希尔排序是在插入排序的基础上对插入排序进行了优化。我们知道插入排序的过程是将后面的要排序的数字依次和待排序前面的数字进行比较,然后判断大小,最后在进行交换。
这就存在一个很大的问题,就是如果最小的数字在最右边的话,按照我们排序的要求(顺序排列)这个最小的数字要依次和前面的n-1个数字进行比较,然后复制交换,所以插入排序的最大的缺点就是复制的次数过多。
实际上我们可以在直接进行插入排序之前对数据进行“处理”,所谓的“处理”就是让数据变得有序一些,不那么随机化,希尔排序也就做了这样一件事情,使用了一个“增量”,用这个“增量”来对待排序的数组进行分组(比如对10个数据进行排序,按照增量为4来分,就可以分别对下标为(0,4,8)(1,5,9)的两组数据进行小规模的排序)在这个小的规模的数组中采用直接插入排序的方法将小的数组排好序,然后将增量减小,再重复进行,最后当增量减小到1的时候就进行最后的一次排序,和我们以前的插入排序是一样的方法,只不过这次插入排序是在经过我们前面处理之后才进行的,进过前面的处理,数据基本上已经达到了有序了,所以在最后一次进行插入排序的时候复制量就减小了很多,大大的提高了效率,时间效率虽然不及快排,但是比直接插入排序还是快了很多。
代码:
package 希尔排序; /** * 希尔排序 * * @author TMs * */ public class ShellSort { public static int count = 0; public static void main(String[] args) { int[] data = new int[] { 5, 3, 6, 2, 1, 9, 4, 8, 7 }; print(data); shellSort(data); print(data); } public static void shellSort(int[] data) { // 计算出最大的h值 int h = 1; while (h <= data.length / 3) { h = h * 3 + 1; } while (h > 0) { for (int i = h; i < data.length; i += h) { if (data[i] < data[i - h]) { int tmp = data[i]; int j = i - h; while (j >= 0 && data[j] > tmp) { data[j + h] = data[j]; j -= h; } data[j + h] = tmp; print(data); } } // 计算出下一个h值 h = (h - 1) / 3; } } public static void print(int[] data) { for (int i = 0; i < data.length; i++) { System.out.print(data[i] + "\t"); } System.out.println(); } }
打印输出结果:
5 3 6 2 1 9 4 8 7 1 3 6 2 5 9 4 8 7 1 2 3 6 5 9 4 8 7 1 2 3 5 6 9 4 8 7 1 2 3 4 5 6 9 8 7 1 2 3 4 5 6 8 9 7 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9
相关推荐
python数据结构与算法分析,希尔排序法实现,希尔排序.py
此希尔排序算法采用增量减半的方法来进行数据的排序,内有部分注释
实现以下常用的内部排序算法并进行性能比较:"直接插入排序"," 折半插入排序"," 2—路插入排序"," 表插入排序"," 希尔排序"," 起泡排序"," 快速排序"," 简单选择排序"," 树形选择排序"," 堆排序"," 归并排序"," 链式...
7大排序算法(快速排序,冒泡排序,选择排序,归并排序,插入排序,希尔排序,堆排序)实现源码
数据结构排序算法中的希尔(shell)排序,可供初学者参考
希尔排序算法Linux下实现 Ubuntu13.04
六种内部排序算法比较:直接插入排序、希尔排序、冒泡排序、快速排序、选择排序、堆排序。包含实验报告和源代码设计。
(1) 完成5种常用内部排序算法的演示,5种排序算法为:快速排序,直接插入排序,选择排序,堆排序,希尔排序; (2) 待排序元素为整数,排序序列存储在数据文件中,要求排序元素不少于30个; (3) 演示程序开始,...
快速排序算法, 希尔排序算法. 排序算法的介绍. C语言实现.
排序算法: 1、插入排序 2、希尔排序 3、冒泡排序 4、快速排序 5、简单选择排序 6、堆排序
C语言实现SHELL排序算法!C语言实现SHELL排序算法!
1、实现KMP模式匹配算法、哈夫曼编码算法、由遍历序列恢复二叉树、Prim算法、Kruskal算法、Floyd算法、Dijkstra算法、拓扑排序、关键路径算法、二叉排序树生成算法(含平衡化)、哈希表生成及哈希查找算法、希尔排序...
希尔排序的源代码; 平台:CentOS release 5.4 (Final) 编译器:GCC 4.3.2
C#算法 -- (三)希尔排序 朋友们,我最近加紧写C#的一些算法。选择排序,插入算法是我已经推出的。现推出希尔排序.今后,如有时间我将依次推出其它的算法编写。 希尔排序是将组分段,进行插入排序. 对想提高C#语言编程...
通过这个程序就可以实现希尔排序,对数据用希尔进行排序
c++平台上实现希尔排序算法,完整的源代码,vc平台运行。
各种常用c++排序算法,包括插入排序、冒泡排序、选择排序、快速排序、归并排序、希尔排序等
希尔排序,冒泡排序、快速排序递归排序,快速排序非递归排序,快速排序改进算法
各种排序算法,包括堆排序,二路归并排序,快速排序,冒泡排序,希尔排序,直接插入排序,直接选择排序
C语言版的希尔排序算法,可以有按照升序、降序两种方式进行排序