• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

C#希尔排序

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

希尔排序(缩小增量法)

  属于插入类排序,是将整个无序列分割成若干小的子序列分别进行插入排序

  排序过程:先取一个正整数d1<n,把所有序号相隔d1的数组元素放一组,组内进行直接插入排序;然后取d2<d1,重复上述分组和排序操作;直至di=1,即所有记录放进一个组中排序为止

  初始:d=5

  49 38 65 97 76 13 27 49* 55 04

  49 13

  |-------------------|

  38 27

  |-------------------|

  65 49*

  |-------------------|

  97 55

  |-------------------|

  76 04

  |-------------------|

  一趟结果

  13 27 49* 55 04 49 38 65 97 76

  d=3

  13 27 49* 55 04 49 38 65 97 76

  13 55 38 76

  |------------|------------|------------|

  27 04 65

  |------------|------------|

  49* 49 97

  |------------|------------|

  二趟结果

  13 04 49* 38 27 49 55 65 97 76

  d=1

  13 04 49* 38 27 49 55 65 97 76

  |----|----|----|----|----|----|----|----|----|

  三趟结果

  04 13 27 38 49* 49 55 65 76 97

  --------------------------------------------------------------------------------------------

  例如对503,17,512,908,170,897,275,653,462,154,509,612,677,765,703,94排序的C语言算法

  ================================================

  功能:希尔排序

  输入:数组名称(也就是数组首地址)、数组中元素个数

  ================================================

  */

  /*

  ====================================================

  算法思想简单描述:

  在直接插入排序算法中,每次插入一个数,使有序序列只增加1个节点,

  并且对插入下一个数没有提供任何帮助。如果比较相隔较远距离(称为

  增量)的数,使得数移动时能跨过多个元素,则进行一次比较就可能消除

  多个元素交换。D.L.shell于1959年在以他名字命名的排序算法中实现

  了这一思想。算法先将要排序的一组数按某个增量d分成若干组,每组中

  记录的下标相差d.对每组中全部元素进行排序,然后再用一个较小的增量

  对它进行,在每组中再进行排序。当增量减到1时,整个要排序的数被分成

  一组,排序完成。

  下面的函数是一个希尔排序算法的一个实现,初次取序列的一半为增量,

  以后每次减半,直到增量为1。

  希尔排序是不稳定的。

 

   C#:代码

  

/// <summary>
/// Dec:Sort Helper
/// Author:david
/// Create Date:2010-05-05
/// </summary>
public class SortHelper
{
/// <summary>
/// Shell Sort
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="array"></param>
public static void ShellSort<T>(T[] array) where T : IComparable
{
int length = array.Length;
for (int h = length / 2; h > 0; h = h / 2)
{
//here is insert sort
for (int i = h; i < length; i++)
{
T temp
= array[i];
if (temp.CompareTo(array[i -h]) < 0)
{
for (int j = 0; j < i; j += h)
{
if (temp.CompareTo(array[j]) < 0)
{
temp
= array[j];
array[j]
= array[i];
array[i]
= temp;
}
}
}
}
}
}
}

测试代码:

 

int[] array = new int[] {23,15,27,90,69,66,158,45,32,1,45,22};
Console.WriteLine(
"before shell sort");
foreach (int i in array)
{
Console.Write(i
+"->");
}
Console.WriteLine();
SortHelper.ShellSort
<int>(array);
Console.WriteLine(
"after shell sort");
foreach (int i in array)
{
Console.Write(i
+ "->");
}
Console.WriteLine();
Console.Read();

 

 

运行结果:

 

before shell sort
23->15->27->90->69->66->158->45->32->1->45->22->
after shell sort
1->15->22->23->27->32->45->45->66->69->90->158->

 

 


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
C#(1)-------发布发布时间:2022-07-14
下一篇:
c# 特性/属性(Attribute) 以及使用反射查看自定义特性发布时间:2022-07-14
热门推荐
热门话题
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap