C#数据结构与算法系列（二十一）：希尔排序算法（ShellSort）
2024-10-09 07:31:37
1.介绍
希尔排序是希尔（Donald Shell）于1959年提出的一种排序算法。希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序。
2.基本思想
希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止
3.示意图
4.代码
using System; namespace DataStructure
{
public class ShellSort
{
/// <summary>
/// 测试希尔排序
/// </summary>
public static void Test()
{
int[] arr = { , , , , , , , , , }; Console.WriteLine("需要排序的数组:" + ArrayToString(arr)); Console.WriteLine("\n封装后的测试"); //测试封装后的希尔排序
Sort(arr); Console.WriteLine("\n封装前的测试"); arr = new int[] { , , , , , , , , , }; int temp = ;
//希尔排序第一轮
//因为第一轮排序，是将十个数据分成了五组
for (int i = ; i < arr.Length; i++)
{
//遍历各组中所有元素（10/2=5）步长五
for (int j = i - ; j >= ; j -= )
{
if (arr[j] > arr[j + ])
{
temp = arr[j]; arr[j] = arr[j + ]; arr[j + ] = temp;
}
}
} Console.WriteLine("\n第一轮希尔排序的结果：" + ArrayToString(arr)); //3,5,1,6,0,8,9,4,7,2 //希尔排序第二轮
//因为第二轮排序，是将十个数据分成了5/2=2组
for (int i = ; i < arr.Length; i++)
{
for (int j = i - ; j >= ; j -= )
{
if (arr[j] > arr[j + ])
{
temp = arr[j]; arr[j] = arr[j + ]; arr[j + ] = temp;
}
}
} Console.WriteLine("\n第二轮希尔排序的结果：" + ArrayToString(arr)); //希尔排序第三轮
//因为第三轮排序，是将十个数据分成了2/2=1组
for (int i = ; i < arr.Length; i++)
{
for (int j = i - ; j >= ; j -= )
{
if (arr[j] > arr[j + ])
{
temp = arr[j]; arr[j] = arr[j + ]; arr[j + ] = temp;
}
}
} Console.WriteLine("\n第三轮希尔排序的结果：" + ArrayToString(arr));
} /// <summary>
/// 封装希尔排序
/// </summary>
/// <param name="arr"></param>
private static void Sort(int[] arr)
{
int temp = ; int count = ;
//遍历各组中的所有元素（共gap组，每组有个元素），步长gap
for (int gap = arr.Length / ; gap > ; gap /= )
{
for (int i = gap; i < arr.Length; i++)
{
for (int j = i - gap; j >= ; j -= gap)
{
//如果当前元素大于加上步长后的那个元素，说明交换
if (arr[j] > arr[j + gap])
{
temp = arr[j]; arr[j] = arr[j + gap]; arr[j + gap] = temp;
}
}
} Console.WriteLine($"\n第{++count }轮希尔排序的结果：{ArrayToString(arr)}");
}
} private static string ArrayToString(int[] arr)
{
return string.Join(",", arr);
}
}
}
5.演示结果
最新文章
- Emgu.CV/opencv 绘图 线面文字包括中文
- SQL Tuning / SQL 性能 优化 调优
- 关于Mesos和Kubernetes的区别
- C++复习-练习-1
- apache.http.MalformedChunkCodingException: Chunked stream ended unexpectedly
- js高级程序设计笔记之-addEventListener()与removeEventListener(),事件解除与绑定
- [HIHO1082]然而沼跃鱼早就看穿了一切（字符串水题）
- kindeditor 上传图片 显示绝对 路径
- ASP.NET验证控件应用实例与详解。
- Jquery LigerUI框架学习（二）之Tree于Tab标签实现iframe功能
- Pycharm
- Codeforces Round #331 (Div. 2) D. Wilbur and Trees 记忆化搜索
- Android SurfaceView实战 带你玩转flabby bird （上）
- gulp-rev-append静态资源添加版本号后缀，清理缓存
- Ubuntu14.04下如何配置固定IP
- 【原创】大叔经验分享（15）spark sql limit实现原理
- 鼠标右键打开命令行cmd(管理员身份）
- Activiti 用户手册
- centos7 update docker
- SQLSERVER2008 存储过程基本语法