C#实现希尔排序
对于大规模乱序的数组，插入排序很慢，因为它只会交换相邻的元素，因此元素只能一点一点地从数组地一段移动到另一端。希尔排序改进了插入排序，交换不相邻地元素以对数组地局部进行排序，最终用插入排序将局部有序的数组排序。
希尔排序的思想是使数组中任意间隔为 h 的元素都是有序的。这样的数组成为 h 有序数组。换句话说，一个 h 有序数组就是 h 个相互独立的有序数组组合在一起的一个数组。
在进行排序时，刚开始 h 很大，就能将元素移动到很远的地方，为实现更小的 h 有序创造方便。h 递减到 1 时，相当于插入排序。这就是希尔排序。下面的代码 h 从 N/3 开始递减，h = h * 3 + 1:
public class Shell: BaseSort
{
public static long usedTimes = 0;
public Shell()
{
}
public static void Sort(IComparable[] a)
{
Stopwatch timer = new Stopwatch();
timer.Start();
int n = a.Length;
int h = 1;
while (h < n / 3)
h = h * 3 + 1;
/*
* 每次循环生成 h有序数组（h 个有序数组） 即 （h 0）, （h+1 1）, （h+2 2）, ....
* 如果右边的值小于左边的值时，交换；
* 并退回到左边的位置，重新排序，循环比较（j>=h）。
* 因为交换可能引起原有序的数组乱序，所以需要退回去重新比较
* 当 h 递减到 1时，相当于插入排序一个部分有序数组
* */
while (h >= 1)
{
//Console.WriteLine(h);
for (int i = h; i < n; i++)
{
//Console.WriteLine(i+","+(i - h));
for (int j = i; j >= h && Less(a[j], a[j - h]); j -= h)
{
Exch(a,j,j-h);
//Console.WriteLine("J:" + (j- h));
}
}
h = h / 3;
}
timer.Stop();
usedTimes = timer.ElapsedMilliseconds;
}
}
从另一个角度看希尔排序，插入排序是将每个比元素大的元素向右移动一个，希尔排序是交换到比它大的元素之前，移动距离从 1 改成 h 。
希尔排序更高效的原因是它将数组变成多个部分有序的数组，减少倒置。排序之初，各个子数组都很短，排序之后子数组都是部分有序的，这很适合插入排序。子数组部分有序的程度取决于递增序列的选择。（如何选择？？）
- 和选择排序以及插入排序对比，希尔排序也可以用于大型数组，即使是随机数字排序也快很多。数组规模越大，对比越明显。
- 希尔排序的性能分析比较困难。它的运行时间达不到平方级别，在最坏情况下的比较次数和 N ^ 3/2 成正比。
- 如果中等大小的数组可以使用希尔排序，它代码量少，且不需要额外的内存空间。
百万级别的排序时间不超过十秒：
count:10000 shell use Milliseconds:6
count:100000 shell use Milliseconds:180
count:1000000 shell use Milliseconds:3226
到此这篇关于C#实现希尔排序的文章就介绍到这了。希望对大家的学习有所帮助，也希望大家多多支持我们。
相关推荐
-
C#实现平衡查找树
目录 1. 2-3查找树 1.查找 2.向 2- 结点中插入新键 3.向一棵只含有一个 3- 结点的树中插入新键 4.向一个父结点为 2- 结点的 3- 结点中插入新键 5.向一个父结点为 3- 结点的 3- 结点插入新键 6.分解根结点 7.局部变换 8.全局性质 2.红黑二叉查找树 1.定义 2.一一对应 3.颜色表示 4.旋转 5.在旋转后重置父结点的链接 6.向单个 2- 结点中插入新键 7.向树底部的 2- 结点插入新键 8.向一棵双键树(即一个 3- 结点)中插入新键 9.颜色变换
-
C#实现优先队列和堆排序
目录 优先队列 1.API 2.初级实现 3.堆的定义 二叉堆表示法 4.堆的算法 上浮(由下至上的堆的有序化) 下沉(由上至下的堆的有序化) 改进 堆排序 1.堆的构造 2.下沉排序 先下沉后上浮 优先队列 许多应用程序都需要处理有序的元素,但不一定要求它们全部有序,或是不一定要一次就将它们排序.很多情况下是收集一些元素,处理当前键值最大的元素,然后再收集更多的元素,再处理当前键值最大的元素.这种情况下,需要的数据结构支持两种操作:删除最大的元素和插入元素.这种数据结构类型叫优先队列. 这里,
-
C#算法之散列表
目录 1.散列函数 正整数 浮点数 字符串 组合键 将 HashCode() 的返回值转化为一个数组索引 自定义的 HashCode 软缓存 2.基于拉链法的散列表 散列表的大小 删除操作 有序性相关的操作 3.基于线性探测法的散列表 删除操作 键簇 线性探测法的性能分析 调整数组大小 拉链法 均摊分析 4.内存的使用 如果所有的键都是小整数,我们可以使用一个数组来实现无序的符号表,将键作为数组的索引而数组中键 i 处存储的就是它对应的值.散列表就是用来处理这种情况,它是简易方法的扩展并能够处理
-
C#实现二叉查找树
目录 1.实现API 1.数据结构 2.查找 3.插入 4.分析 有序性相关的方法和删除操作 1.最大键和最小键 2.向上取整和向下取整 3.选择操作 4.排名 5.删除最大键和删除最小键 6.删除操作 7.范围查找 8.性能分析 对于符号表,要支持高效的插入操作,就需要一种链式结构.但单链表无法使用二分查找,因为二分查找的高效来自于能够快速通过索引取得任何子数组的中间元素,链表只能遍历(详细描述).为了将二分查找的效率和链表的灵活性结合,需要更复杂的数据结构:二叉查找树.具体来说,就是使用每个
-
C#实现快速排序算法
快速排序是应用最广泛的排序算法,流行的原因是它实现简单,适用于各种不同情况的输入数据且在一般情况下比其他排序都快得多. 快速排序是原地排序(只需要一个很小的辅助栈),将长度为 N 的数组排序所需的时间和 N lg N 成正比. 1.算法 快速排序也是一种分治的排序算法.它将一个数组分成两个子数组,将两部分独立地排序. 快速排序和归并排序是互补:归并排序是将数组分成两个子数组分别排序,并将有序数组归并,这样数组就是有序的了:而快速排序将数组通过切分变成部分有序数组,然后拆成成两个子数组,当两个子数
-
C#使用符号表实现查找算法
高效检索海量信息(经典查找算法)是现代信息世界的基础设施.我们使用符号表描述一张抽象的表格,将信息(值)存储在其中,然后按照指定的键来搜索并获取这些信息.键和值的具体意义取决于不同的应用.符号表中可能会保存很多键和很多信息,因此实现一张高效的符号表是很重要的任务. 符号表有时被称为字典,有时被称为索引. 1.符号表 符号表是一种存储键值对的数据结构,支持两种操作:插入(put),即将一组新的键值对存入表中:查找(get),即根据给定的键得到相应的值.符号表最主要的目的就是将一个健和一个值联系起来
-
JavaScript排序算法之希尔排序的2个实例
插入排序在对几乎已经排好序的数据操作时, 效率高, 即可以达到线性排序的效率.但插入排序一般来说是低效的, 因为插入排序每次只能将数据移动一位.希尔排序按其设计者希尔(Donald Shell)的名字命名,该算法由1959年公布.一些老版本教科书和参考手册把该算法命名为Shell-Metzner,即包含Marlene Metzner Norton的名字,但是根据Metzner本人的说法,"我没有为这种算法做任何事,我的名字不应该出现在算法的名字中." 希尔排序基本思想:先取一个小于n的
-
java 数据结构基本算法希尔排序
C语言数据结构基本算法希尔排序 前言: 基本思想:算法先将要排序的一组数按某个增量d(n/2,n为要排序数的个数)分成若干组,每组中记录的下标相差d.对每组中全部元素进行直接插入排序, 然后再用一个较小的增量(d/2)对它进行分组,在每组中再进行直接插入排序.当增量减到1时,进行直接插入排序后,排序完成. 实现代码: public class ShellSort { /** * 原理:算法先将要排序的一组数按某个增量d(n/2,n为要排序数的个数)分成若干组,每组中记录的 * 下标相差d.对每组
-
用Java实现希尔排序的示例
一.理论准备 希尔排序(Shell Sort)是插入排序的一种,是针对直接插入排序算法的改进,是将整个无序列分割成若干小的子序列分别进行插入排序,希尔排序并不稳定.该方法又称缩小增量排序,因DL．Shell于1959年提出而得名.基本思想:先取一个小于n的整数d1作为第一个增量,把文件的全部记录分成d1个组.所有距离为d1的倍数的记录放在同一个组中.先在各组内进行直接插入排序:然后,取第二个增量d2<d1重复上述的分组和排序,直至所取的增量dt=1(dt<dt-l<-<d2<
-
java高级排序之希尔排序
希尔排序对于多达几千个数据项的,中等大小规模的数组排序表现良好,希尔排序不像快速排序和其它时间复杂度为O(n*logn)的排序算法那么快,因此,对非常大的文件排序,它不是最优选择,但是希尔排序比选择排序和插入排序这种时间复杂度为O(n²)的排序要快的多,并且它非常容易实现,代码简短 希尔排序也是插入排序的一种,在插入排序中,如果最小的数在最后面,则复制的次数太多,而希尔解决了这个问题,它也是n-增量排序,它的思想是通过加大插入排序中元素的间隔,并在这些有间隔的元素中进行插入排序,当这些数据项排过
-
Java实现八个常用的排序算法：插入排序、冒泡排序、选择排序、希尔排序等
本文实现了八个常用的排序算法:插入排序.冒泡排序.选择排序.希尔排序 .快速排序.归并排序.堆排序和LST基数排序 首先是EightAlgorithms.java文件,代码如下: import java.util.Arrays; /* * 实现了八个常用的排序算法:插入排序.冒泡排序.选择排序.希尔排序 * 以及快速排序.归并排序.堆排序和LST基数排序 * @author gkh178 */ public class EightAlgorithms { //插入排序:时间复杂度o(n^2) p
-
python实现的希尔排序算法实例
本文实例讲述了python实现希尔排序算法的方法.分享给大家供大家参考.具体如下: 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] j -= inc items[j] = temp inc = inc/2
-
Swift编程中实现希尔排序算法的代码实例
思想 希尔排序的实质就是分组插入排序,该方法又称缩小增量排序,因DL．Shell于1959年提出而得名. 该方法的基本思想是:先将整个待排元素序列分割成若干个子序列(由相隔某个"增量"的元素组成的)分别进行直接插入排序,然后依次缩减增量再进行排序,待整个序列中的元素基本有序(增量足够小)时,再对全体元素进行一次直接插入排序.因为直接插入排序在元素基本有序的情况下(接近最好情况),效率是很高的,因此希尔排序在时间效率上比前两种方法有较大提高. 以n=10的一个数组49, 38, 65,
-
JavaScript希尔排序、快速排序、归并排序算法
以var a = [4,2,6,3,1,9,5,7,8,0];为例子. 1.希尔排序. 希尔排序是在插入排序上面做的升级.是先跟距离较远的进行比较的一些方法. function shellsort(arr){ var i,k,j,len=arr.length,gap = Math.ceil(len/2),temp; while(gap>0){ for (var k = 0; k < gap; k++) { var tagArr = []; tagArr.push(arr[k]) for (i
-
c语言实现冒泡排序、希尔排序等多种算法示例
实现以下排序 插入排序O(n^2) 冒泡排序 O(n^2) 选择排序 O(n^2) 快速排序 O(n log n) 堆排序 O(n log n) 归并排序 O(n log n) 希尔排序 O(n^1.25) 1.插入排序 O(n^2) 一般来说,插入排序都采用in-place在数组上实现.具体算法描述如下:⒈ 从第一个元素开始,该元素可以认为已经被排序⒉ 取出下一个元素,在已经排序的元素序列中从后向前扫描⒊ 如果该元素(已排序)大于新元素,将该元素移到下一位置⒋ 重复步骤3,直到找到已排序的元素
-
细致解读希尔排序算法与相关的Java代码实现
希尔排序(Shell's sort)是一种非常"神奇"的排序算法.说它"神奇",是因为没有任何人能清楚地说明它的性能到底能到什么情况.希尔排序因DL．Shell于1959年提出而得名.自从C. A. R. Hoare在1962年提出快速排序后,由于其更为简单,一般采用快速排序.但是,不少数学家们还是孜孜不倦地寻找希尔排序的最佳复杂度.作为普通程序员,我们可以学习下希尔的思路. 顺便说一句,在希尔排序出现之前,计算机界普遍存在"排序算法不可能突破O(n2)&