希尔排序
*尔排序属于插入类排序,是将整个有序序列分割成若干小的子序列分别进行插入排序。
*排序过程:先取一个正整数d1<n,把所有序号相隔d1的数组元素放一组,组内进行直接插入排序;然后取d2<d1,
*重复上述分组和排序操作;直至di=1,即所有记录放进一个组中排序为止。
*
*希尔排序是按照不同步长对元素进行插入排序,当刚开始元素很无序的时候,步长最大,所以插入排序的元素个数很少,
*速度很快;当元素基本有序了,步长很小,插入排序对于有序的序列效率很高。
*所以,希尔排序的时间复杂度会比o(n^2)好一些。由于多次插入排序,我们知道一次插入排序是稳定的,
*不会改变相同元素的相对顺序,但在不同的插入排序过程中,相同的元素可能在各自的插入排序中移动,
*最后其稳定性就会被打乱,所以shell排序是不稳定的。
package com.algorithm; /** * 希尔排序 * @author lenovo *尔排序属于插入类排序,是将整个有序序列分割成若干小的子序列分别进行插入排序。 *排序过程:先取一个正整数d1<n,把所有序号相隔d1的数组元素放一组,组内进行直接插入排序;然后取d2<d1, *重复上述分组和排序操作;直至di=1,即所有记录放进一个组中排序为止。 * *希尔排序是按照不同步长对元素进行插入排序,当刚开始元素很无序的时候,步长最大,所以插入排序的元素个数很少, *速度很快;当元素基本有序了,步长很小,插入排序对于有序的序列效率很高。 *所以,希尔排序的时间复杂度会比o(n^2)好一些。由于多次插入排序,我们知道一次插入排序是稳定的, *不会改变相同元素的相对顺序,但在不同的插入排序过程中,相同的元素可能在各自的插入排序中移动, *最后其稳定性就会被打乱,所以shell排序是不稳定的。 */ public class ShellSort { /** * 排序方法 */ public static void sort(long[] attr){ //初始化一个间隔 int h=1; //计算最大间隔 while (h<attr.length/3) { h=h*3+1; } while(h>0){ //进行插入排序 long temp=0; for (int i = h; i < attr.length; i++) { temp =attr[i]; int j=i; while (j>h-1&&attr[j-h]>=temp) { attr[j]=attr[j-h]; j =j-h; } attr[j]=temp; } //减小间隔 h=(h-1)/3; } } public static void main(String[] args) { long[] attr = new long[5]; attr[0]=34; attr[1]=23; attr[2]=2; attr[3]=55; attr[4]=1; System.out.print("{"); for (int i = 0; i < attr.length; i++) { System.out.print(attr[i]+" "); } System.out.println("}\n"); sort(attr); System.out.print("{"); for (int i = 0; i < attr.length; i++) { System.out.print(attr[i]+" "); } System.out.println("}\n"); } }
相关推荐
(1) 完成5种常用内部排序算法的演示,5种排序算法为:快速排序,直接插入排序,选择排序,堆排序,希尔排序; (2) 待排序元素为整数,排序序列存储在数据文件中,要求排序元素不少于30个; (3) 演示程序开始,...
一个数据结构作业,对刚刚学习希尔排序知识的同学有用,用C++做的
合并排序,插入排序,希尔排序,快速排序,冒泡排序,桶排序的C语言实现,原创。
希尔排序 希尔排序希尔排序希尔排序希尔排序希尔排序希尔排序希尔排序
实现以下常用的内部排序算法并进行性能比较:"直接插入排序"," 折半插入排序"," 2—路插入排序"," 表插入排序"," 希尔排序"," 起泡排序"," 快速排序"," 简单选择排序"," 树形选择排序"," 堆排序"," 归并排序"," 链式...
希尔排序的源代码; 平台:CentOS release 5.4 (Final) 编译器:GCC 4.3.2
用C++,模板写的 7中排序. 快速排序, 归并排序,插入排序,选择排序,起泡排序,堆排序,希尔排序
数据结构 综合排序 冒泡排序 直接插入排序 快速排序 希尔排序,完整的代码,有每种排序时间的比较
此希尔排序算法采用增量减半的方法来进行数据的排序,内有部分注释
排序算法: 1、插入排序 2、希尔排序 3、冒泡排序 4、快速排序 5、简单选择排序 6、堆排序
1) 至少采用三种方法实现上述问题求解(提示,可采用的方法有插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序、归并排序)。并把排序后的结果保存在不同的文件中。 2) 统计每一种排序方法的性能(以上机...
希尔排序法,最经典的排序法,但不是容易懂。包括希尔插入排序,希尔交换排序
排序算法很多,下面有基数排序,堆排序,希尔排序,直接插入排序的代码和思路
本实验含有四部分内容——直接插入排序、希尔排序、选择排序、快速排序,在上述内容的基础上,将所有排序算法整合在一个程序中。学生可参考教材中的伪代码。鼓励学生自创新思路,新算法。
就利用汇编版的希尔排序来写了一下超级列表框排序.发现,从取值-排序-显示过程才花了1秒的时间.速度是七号排序的30倍,凌晨孤星-超级列表框排序的3倍.而这个希尔排序模块.只用增加,删减自定义数据类型成员.即可变身另...
7大排序算法(快速排序,冒泡排序,选择排序,归并排序,插入排序,希尔排序,堆排序)实现源码
希尔排序,堆排序,快速排序,简单选择排序,插入排序,冒泡排序
插入排序之希尔排序
了解冒泡,选择,插入,希尔排序 基本的渐进分析
希尔排序(程序).txt希尔排序(程序).txt希尔排序(程序).txt