[4] 算法之路 - 插入排序之Shell间隔与Sedgewick间隔

题目

插入排序法由未排序的后半部前端取出一个值,插入已排序前半部的适当位置,概念简单但速度不快。

排序要加快的基本原则之一:

是让后一次的排序进行时,尽量利用前一次排序后的结果,以加快排序的速度,Shell排序法即是基于此一概念来改良插入排序法。

解法

Shell排序法最初是D.L Shell于1959所提出,假设要排序的元素有n个,则每次进行插入排序时并不是所有的元素同时进行时,而是取一段间隔。

Shell排序算法 – n/2间隔

Shell首先将间隔设定为n/2,然后跳跃进行插入排序,再来将间隔n/4,跳跃进行排序动作,再来间隔设定为n/8、n/16,直到间隔为1之后的最后一次排序终止。

Shell排序算法 – Sedgewick间隔

将间隔设定为n / 2是D.L Shell最初所提出,在教科书中使用这个间隔比较好说明,然而Shell排序法的关键在于间隔的选定,例如Sedgewick证明选用以下的间隔可以加 快Shell排序法的速度:

e.g 对于一个长度为10000的整型数组,

Swedge[0]=10000, Swedge[1]=2537, Swedge[2]=653, Swedge[4]=48,Swedge[5]=15…Swedge[8]=1

采用Swedge间隔需要迭代8次 (Swedge[0] 不使用)

而用普通Shell间隔需要迭代13次

Comsh [0]=10000, Comsh [1]=5000, Comshe[2]=2500, Comsh[4]=625,…..Comshell[8]=39, Comshell[13]=1

后来还有人证明有其它的间隔选定法可以将Shell排序法的速度再加快;另外Shell排序法的概念也可以用来改良气泡排序法。

SourceCodes

n/2间隔与Sedgewick间隔的 Shell排序

int DLShellSort(int a[],int lens)
{
	for(int gap=lens/2;gap>0;gap/=2)
	{
		InsertionSortWithGap(a,lens,gap);
	}
	return 0;
}

// 4*((2^j)^2)+3*(2^j)+1<=n
// j= log(((-3+sqrt(16*lens-7.0))/8))/log(2.0)
int SedgewickShellSort(int a[],int lens)
{
	int sdwindex= (int)log(((-3+sqrt(16*lens-7.0))/8))/log(2.0);
	int sdwpr=(int)pow(2,(double)sdwindex);
	int sdwpr2=sdwpr/2;
	while(true)
	{
		int sdwgap=4*sdwpr2*sdwpr2+3*sdwpr2+1;
		InsertionSortWithGap(a,lens,sdwgap);
		sdwpr2/=2;
		if(sdwpr2<=1)break;
	}
	return 0;
}

见 [3] 算法之路 - 插入排序

// 插入排序 使用指定间隔的
int InsertionSortWithGap(int a[],int lens,int gap)
{
	int k,tmp;
	// 控制插入层
	for(int m=0;m<gap;m++)
	{
		for(int i=gap+m;i<lens;i+=gap)
		{
			int j=i-gap;
			tmp=a[i];
			for(k=j;k>=0;k-=gap)
			{
				if(tmp<a[k]) a[k+gap]=a[k];
				else break;
			}
			if(i!=(k+gap))a[k+gap]=tmp;
		}
	}
	return 0;
}

[4] 算法之路 - 插入排序之Shell间隔与Sedgewick间隔,布布扣,bubuko.com

时间: 08-20

[4] 算法之路 - 插入排序之Shell间隔与Sedgewick间隔的相关文章

[3] 算法之路 - 插入排序

插入排序 – 算法 1.将排序部分分成两部分 2.每次从后面部分取最前面的数插入到前面部分的适当位置 该处提供两个插入排序版本,指定间隔插入与插入排序.后面对指定间隔排序提到Shell排序中的n/2间隔与Sedgewick间隔 例如: 排序前:92 77 67 8 6 84 55 85 43 67 [77 92] 67 8 6 8455 85 43 67 将77插入92前 [67 77 92] 8 6 8455 85 43 67 将67插入77前 [8 67 77 92] 6 8455 85 4

七大内部排序算法总结(插入排序、希尔排序、冒泡排序、简单选择排序、快速排序、归并排序、堆排序)

 写在前面: 排序是计算机程序设计中的一种重要操作,它的功能是将一个数据元素的任意序列,重新排列成一个按关键字有序的序列.因此排序掌握各种排序算法非常重要.对下面介绍的各个排序,我们假定所有排序的关键字都是整数.对传入函数的参数默认是已经检查好了的.只是简单的描述各个算法并给出了具体实现代码,并未做其他深究探讨. 基础知识: 由于待排序的记录数量不同,使得排序过程中设计的存储器不同,可将排序方法分为两大类:一类是内部排序,指的是待排序记录存放在计算机随机存储器中进行的排序过程.另一类是外部排序,

算法学习-1 插入排序

算法学习-1  插入排序 一.描述: 比如说我们玩扑克牌,规定每抓一张牌都要保证左边数字最小:抓第一张牌直接放手里就可以,抓第二张时如果比第一张小,则把它放到第一张牌的左边,假如每张抓来的牌放到手中都有固定位置,第一张为A[0],第二张为A[1],第三张为A[2],如果抓的第三张牌比第一张抓来的牌小,则将其放在A[0]处,对应的第二张牌就应该放在A[1],以此类推. 二.java代码实现 public class InsertSort { //排序后的数组 int sorted[]; publi

[1] 算法之路 - 选择排序

选择排序 – 算法 1. 将要排序的对象分作2部份,一个是已排序的,一个是未排序的 2.  从后端未排序部份选择一个最小值,并放入前端已排序部份的最后一个 e.g: 排序前:70 80 31 37 10 1 48 60 33 80 [1] 80 31 37 10 7048 60 33 80 选出最小值1 [1 10] 31 37 80 7048 60 33 80 选出最小值10 [1 10 31] 37 80 7048 60 33 80 选出最小值31 [1 10 31 33] 80 7048

[2] 算法之路 - 选择之堆排序

题目: 选择排序法的概念简单,每次从未排序部份选一最小值,插入已排序部份的后端,其时间主要花费于在整个未排序部份寻找最小值,如果能让搜寻最小值的方式加 快,选择排序法的速率也就可以加快 Heap排序法让搜寻的路径由树根至最后一个树叶,而不是整个未排序部份,从而可以加快排序的过程,因而称之为改良的选择排序法. 整个堆排序的过程分建堆.取值.调整为新的堆三个过程.分别如下示:(以最小堆积树为例.关于HeapTree请参阅数据结构与算法) 建堆 - 算法 1.  加至堆积树的元素会先放置在最后一个树叶

[6] 算法之路 - 双向冒泡排序之Shaker

Shaker排序 –算法 1. 气泡排序的双向进行,先让气泡排序由左向右进行,再来让气泡排序由右往左进行,如此完成一次排序的动作 2. 使用left与right两个旗标来记录左右两端已排序的元素位置. 一个排序的例子如下所示: 排序前:45 19 77 81 13 28 18 1977 11 往右排序:19 45 77 13 28 18 19 7711 [81] 向左排序:[11] 19 45 77 13 28 1819 77 [81] 往右排序:[11] 19 45 13 28 18 19[7

JavaScript ,Python,Go,java,C#系列算法之【插入排序】篇

常见的内部排序算法有:插入排序.希尔排序.选择排序.冒泡排序.归并排序.快速排序.堆排序.基数排序等.用一张图概括: 插入排序 插入排序(英语:Insertion Sort)是一种简单直观的排序算法.它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入.插入排序在实现上,通常采用in-place排序(即只需用到O(1)的额外空间的排序),因而在从后向前扫描过程中,需要反复把已排序元素逐步向后挪位,为最新元素提供插入空间. 插入排序和冒泡排序一样,也有一种

排序算法之 Java插入排序算法

package net.qh.test.sort; import java.util.ArrayList; import java.util.Calendar; import java.util.List; /** * Created by Administrator on 2016/03/01. */ public class Insert { public int[] sort(int[] arr){ if ( arr == null || arr.length <= 1 ){ return

[7] 算法之路 - 快速排序之3轴演算

左轴演算.中轴演算.右轴演算 题目: 快速排序法(quick sort)是目前所公认最快的排序方法之一(视解题的对象而定),虽然快速排序法在最差状况下可以达O(n2),但是在多数的情况下,快速排序法的效率表现是相当不错的. 快速排序 - 算法 1.快速排序法的基本精神是在数列中找出适当的轴心,然后将数列一分为二 2.分别对左边与右边数列进行排序 左轴演算: // 快速排序 - 左轴演算 // 1. 附设两个指针left/right,并设最左端的数为最初枢轴pivot // 2. 从右向左搜索,找