希尔排序【模板】

希尔排序用了用了更少的时间编出来:

#include <iostream>

void Shellsort(int A[],int p,int r)
{
	int d=r-p+1;	//将 length(A) 赋给d

	int i,j,tmp;
	while(d>=1)
	{
		d/=2;
		for(i=p+d;i<=r;i++)
		{
			tmp=A[i];
			j=i-d;		//从i的前一个步长开始
			while(j>=p && tmp<A[j])
			{
				A[j+d]=A[j];	//记录后移
				j-=d;			//向前计数
			}

			A[j+d]=tmp;
		}
	}
}

int main()
{
	int A[6]={0,5,3,2,1,4};

	Shellsort(A,1,5);

	for(int i=1;i<=5;i++)
		printf("%d ",A[i]);

	return 0;
}

运行结果为:

1 2 3 4 5

时间: 2013-10-30

希尔排序【模板】的相关文章

python实现的希尔排序算法实例

  本文实例讲述了python实现希尔排序算法的方法.分享给大家供大家参考.具体如下: ? 1 2 3 4 5 6 7 8 9 10 11 12 13 14 def shellSort(items): inc = len(items) / 2 while inc: for i in xrange(len(items)): j = i temp = items[i] while j >= inc and items[j-inc] > temp: items[j] = items[j - inc]

C#算法----(三)希尔排序 (solarsoft原创)

朋友们,我最近加紧写C#的一些算法.选择排序,插入算法是我已经推出的.现推出希尔排序.今后,如有时间我将依次推出其它的算法编写.希尔排序是将组分段,进行插入排序.对想提高C#语言编程能力的朋友,我们可以互相探讨一下.如:下面的程序,并没有实现多态,来,帮它实现一下.using System;public class ShellSorter{  public void Sort(int [] list)  {      int inc;      for(inc=1;inc<=list.Lengt

C#的四种排序算法:冒泡排序、选择排序、插入排序和希尔排序

插入|排序|算法 本文介绍了C#的四种排序算法:冒泡排序.选择排序.插入排序和希尔排序 冒泡排序 using System: namespace BubbleSorter { public class BubbleSorter { public void Sort(int [] list) { int i,j,temp: bool done=false: j=1: while((j<list.Length)&&(!done)) { done=true: for(i=0:i<li

内部排序:插入排序和希尔排序的N种实现

前言 本来想将所有的内部排序总结为一篇博文,但是随着研究的深入,还是放弃了这个念头,斟前酌后,还是觉得分开来写比较好,具体原因,看完本篇博文也就自然明了了. 本篇文章主要探讨插入排序和希尔排序,之所将二者放在一起,很明显,是因为希尔排序是建立在插入排序的基础之上的. 注:以下各排序算法的N种实现方法大部分都是我根据算法思想,自己写出来的,或者是参考其本身的经典实现,我自己都已测试通过,但不敢保证一定都没问题,如果有疑问,欢迎指出. 插入排序 插入排序的思想很简单,它的基本操作就是将一个数据插入到

java中实现希尔排序算法

package Utils.Sort; /**   *希尔排序,要求待排序的数组必须实现Comparable接口   */   public class ShellSort implements SortStrategy   {   private int[] increment; /**   *利用希尔排序算法对数组obj进行排序   */   public void sort(Comparable[] obj)   {   if (obj == null)   {   throw new N

希尔排序算法的实现

希尔排序(shellsort)又叫增量递减(diminishing increment)排序,是由D.L. Shell发明的,这个算法是通过一个逐渐减小的增量使一个数组逐渐趋近于有序从而达到排序的目的. 假设有一个数组int data[16] = {...}. 首先将这个增量设为16 / 2 = 8,这样就将这个数组分成了8个子数组,它们的索引是0, 8    1, 9   2, 10等等 .对这些子数组进行排序.然后再使增量为8 / 2 = 4,这样就将原数组分成了4个子数组,它们的索引分别是

经典算法(3) 希尔排序的实现

希尔排序的实质就是分组插入排序,该方法又称缩小增量排序,因DL.Shell于1959年提出而得名. 该方法的基本思想是:先将整个待排元素序列分割成若干个子序列(由相隔某个"增量"的元素组成 的)分别进行直接插入排序,然后依次缩减增量再进行排序,待整个序列中的元素基本有序(增量足够小) 时,再对全体元素进行一次直接插入排序.因为直接插入排序在元素基本有序的情况下(接近最好情况), 效率是很高的,因此希尔排序在时间效率上比前两种方法有较大提高. 以n=10的一个数组49, 38, 65,

算法速成(三)七大经典排序之直接插入排序、希尔排序和归并排序

直接插入排序: 这种排序其实蛮好理解的,很现实的例子就是俺们斗地主,当我们抓到一 手乱牌时,我们就要按照大小梳理扑克,30秒后, 扑克梳理完毕,4条3,5条s,哇塞......  回忆一下,俺们当时是怎么梳理的. 最左一张牌是3,第二张牌是5,第三张牌又是3, 赶紧插到第一张牌后面去,第四张牌又是3,大喜,赶紧插到第二张后面去, 第五张牌又是3, 狂喜,哈哈,一门炮就这样产生了. 怎么样,生活中处处都是算法,早已经融入我们的生活和 血液. 下面就上图说明: 看这张图不知道大家可否理解了,在插入排

希尔排序

希尔排序是插入排序的一种(分组+直接插入排序) 一 算法思想 先取一个小于n的整数d1作为第一个增量,把文件的全部记录分成d1个组.所有距离为dl的倍数的记录放在同一个组中.先在各组内进行直接插人排序:然后,取第二个增量d2<d1重复上述的分组和排序,直至所取的增量dt=1(dt<dt-l<-<d2<d1),即所有记录放在同一组中进行直接插入排序为止. [cpp] view plain copy void ShellPass(SeqList R,int d)     {//希