希尔排序(Shell Sort)
希尔排序(Shell Sort)是插入排序的一种。也称缩小增量排序,是直接插入排序算法的一种更高效的改进版本。希尔序是非稳定排序算法。该方法因DL.Shell于1959年提出而得名。希尔排序是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序;随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个文件恰被分成一组,算法便终止。
步骤:
1.先取一个小于n的整数d1作为第一个增量,把文件的全部记录分组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插
2.入排序;然后,取第二个增量d2<d1重复上述的分组和排序,直至所取的增量
=1(
<
…<d2<d1),即所有记录放在同一组中进行
3.直接插入排序为止。
实质
比较相隔较远距离(称为增量)的数,使得数移动时能跨过多个元素,则进行一次比[2] 较就可能消除多个元素交换。算法先将要排序的一组数按某个增量d分成若干组,每组中记录的下标相差d.对每组中全部元素进行排序,然后再用一个较小的增量对它进行,在每组中再进行排序。当增量减到1时,整个要排序的数被分成一组,排序完成。一般的初次取序列的一半为增量,以后每次减半,直到增量为1。
实例分析
以4为关键字进行分组
每组两个端点比较大小,头端点比尾端点大的话交换位置,否则不变
第一组【45,34,78,12,34】位置交换后变为:【34,34,78,12,45】
第二组【34,78,12,34,32】位置交换后变为:【32,78,12,34,34】
第三组【78,12,34,32,29】位置交换后变为:【29,12,34,32,78】
第四组【12,34,32,29,64】位置不变
第一轮分组后序列为
第二轮分组以2为关键字
每组两个端点比较大小,头端点比尾端点大的话交换位置,否则不变
第一组【34,32,29】位置交换后变为【29,32,34】
整体序列为 29, 32, 34, 12,45,34,78,64
第二组【32,34,12】位置交换后变为【12,34,32】
整体序列为 29, 12, 34, 32,45,34,78,64
第三组【34,32,45】保持不变
第四组【32,45,34】保持不变
第五组【45,34,78】保持不变
第六组【34,78,64】保持不变
即 29, 12, 34, 32,45,34,78,64
第三轮以1为关键字进行分组
【29,12】位置变换之后【12,29】
【29,34】位置不变
【34,32】位置变换之后【32,34】
【34,45】位置不变
【45,34】位置变化之后【34,45】
【45,78】位置不变
【78,64】位置变化之后【64,78】
最终序列为
12,29,32,34,34,45,64,78 至此排序完毕
java代码以【8,3,2,1,7,4,6,5】序列为例
package com.yonyou.test; /** * 内部排序算法之Shell排序 * 默认按照从小到大进行排序操作 */ public class Test{ public static void main(String[] args) { //需要进行排序的数组 int[] array=new int[]{8,3,2,1,7,4,6,5}; //输出原数组的内容 printResult(array); //shell排序操作 shellSort(array); //输出排序后的相关结果 printResult(array); } /** * shell排序算法 * 增量h=(h*3)+1; 这个增量公式是由Knuth给出的 * @param array */ private static void shellSort(int[] array) { //首先根据数组的长度确定增量的最大值 int h=1; // 按h * 3 + 1得到增量序列的最大值 while(h <= array.length / 3) { h = h * 3 + 1; } //进行增量查找和排序 while(h>0) { for(int i=h;i<array.length;i++) { for(int k=i;k<array.length;k+=h) { //判断是否需要重新排序,如果小于k-h处的值,需要重新排序 if(array[k]<array[k-h]) { int tempValue=array[k]; int j=k; for(;j>=i&&tempValue<array[j-h];j-=h) { array[j]=array[j-h]; } array[j]=tempValue; } } printResult(array); } h=(h-1)/3; } } /** * 输出相应数组的结果 * @param array */ private static void printResult(int[] array) { for(int value:array) System.out.print(" "+value+" "); System.out.println(); } /** * 交换数组中两个变量的值 * @param array * @param i * @param j */ private static void swap(int[] array,int i,int j){ int temp=array[i]; array[i]=array[j]; array[j]=temp; } }
算法分析
- 1.不稳定
- 2.空间代价θ(1)
- 3.时间代价θ(n²)
- 4.选择适当的增量序列,可以使得时间代价解决θ(n)
相关推荐
自己实现的shell算法,参考C program language里面的
shell排序shell排序shell排序shell排序shell排序shell排序shell排序
K-shell 分解方法给出了节点重要性的一种粗粒化的划分。 其基本思想如下,假设边缘节点的 K-shell值为 1,然后往内一层层进入网络的核心,先去除网络 中度值等于 1 的所有节点以及连边。 若剩下的节点里面,仍有度值...
基于python-2.7实现的K-Shell节点排序算法,算法结果输出每个节点K值。
根据k-shell算法,对网络进行划分,得到每一层的子网
鉴于当前众多方法在识别节点的不同影响力时存在一定局限性,因此在k-shell方法的基础上,通过度量边的潜在重要性,考虑邻居节点的差异贡献性,从而定义了节点的加权度概念,并提出了MKS(Modified k-shell)算法,该...
算法利用节点的[k]-shell值进行网络划分并引导搜索路径,利用超点聚合处理[k]-shell子网来降低路径搜索中节点和连边的规模,通过在路径搜索过程使用双向搜索树方法提高算法的计算效率和准确率。实验结果表明,算法...
shell排序的c语言算法 很好很强大很高效很教授的算法
本文件包含shell排序的基本思路,代码实现,时间复杂度的分析。对数据结构与算法中shell排序算法的实现,附件以python实现。
simotion中的一种算法。simotion是全球最新的运动控制系统
Python手撕算法ShellSort
这个试用shell实现的排序算法间大名了
void ShellSort(T a[],size_t a_size,size_t dlta[],size_t dlta_size) { for(int i=0;i!=dlta_size;++i) ShellInsert(a,a_size,dlta[i]); } int main() { int inta[]={7,1,3,4,5,10,2,6,9,8}; ...
冒泡 插入 选择排序
排序算法 排序算法_基于C语言实现的排序算法之ShellSort实现
7-2算法ShellSort1
算法利用节点的 k-shell 值进行网络划分并引导搜索路径,利用超点聚合处理 k-shell 子网来降低路径搜索中节点和连边的规模,通过在路径搜索过程使用双向搜索树方法提高算法的计算效率和准确 率。实验表明,算法通用...
学习shell脚本,了解linux知识。
数据结构课程排序算法中的经典shell排序
Shell(希尔)排序算法C语言源程序,算法思路:比如对4个数进行排序,4个数分为两组,然后第1个数与第3个数进行比较,第2个数与第4个数进行比较,调整位置,然后将经过调整后的第2位与第3位再进行比较 。