27.排序-希尔排序
27.1 知识点
希尔排序的基本原理
- 希尔排序是插入排序的升级版，必须先掌握插入排序。
- 希尔排序的原理：
- 将整个待排序序列分割成若干子序列。
- 分别对子序列进行插入排序。
总而言之，希尔排序对插入排序的升级主要就是加入了一个步长的概念：
- 通过步长每次可以把原序列分为多个子序列。
- 对子序列进行插入排序。
- 在极限情况下可以有效降低普通插入排序的时间复杂度，提升算法效率。
通俗理解：
- 每轮确定一个步长，这个步长决定将当前要排序的元素分成多少个子数组。
- 在子数组中分别进行插入排序。
- 步长逐渐减小，直到等于1，就可以说不分组了，最后再对整个数组进行插入排序。
代码实现
前提条件
- 学习希尔排序的前提条件：先掌握插入排序。
希尔排序实例
实现升序排序：[8, 7, 1, 5, 4, 2, 6, 3, 9]，将大的元素放在最后面。
// 创建无序数组
int[] array = new int[] { 8, 7, 1, 5, 4, 2, 6, 3, 9 };
// 希尔排序核心代码
// 第一步：实现插入排序
for (int step = array.Length / 2; step > 0; step /= 2)
{
// 第二步：确定步长
// 第三步：执行插入排序
for (int i = step; i < array.Length; i++)
{
int nowSortNum = array[i];
int sortIndex = i - step;
while (sortIndex >= 0 && array[sortIndex] > nowSortNum)
{
array[sortIndex + step] = array[sortIndex];
sortIndex -= step;
}
array[sortIndex + step] = nowSortNum;
}
}
// 打印输出
for (int i = 0; i < array.Length; i++)
{
Console.WriteLine(array[i]);
// 1
// 2
// 3
// 4
// 5
// 6
// 7
// 8
// 9
}
总结
- 基本原理：
- 设置步长。
- 步长不停缩小，直到为1排序后结束。
- 具体排序方式：
- 插入排序原理。
- 套路写法：
- 三层循环。
- 一层获取步长。
- 一层获取未排序区元素。
- 一层找到合适位置插入。
- 注意事项：
- 步长确定后，会将所有子序列进行插入排序。
27.2 知识点代码
using System;
namespace Lesson26_希尔排序
{
class Program
{
static void Main(string[] args)
{
Console.WriteLine("希尔排序");
#region 知识点一 希尔排序的基本原理
//希尔排序是
//插入排序的升级版
//必须先掌握插入排序
//希尔排序的原理
//将整个待排序序列
//分割成为若干子序列
//分别进行插入排序
//总而言之
//希尔排序对插入排序的升级主要就是加入了一个步长的概念
//通过步长每次可以把原序列分为多个子序列
//对子序列进行插入排序
//在极限情况下可以有效降低普通插入排序的时间复杂度
//提升算法效率
//通俗理解
//每轮确定一个步长 这个步长决定把当前要排序元素分成多少个子数组
//在子数组分别进行插入排序
//步长会逐渐减小 直到等于1 就可以说不分组了
//最后再对整个数组进行插入排序
#endregion
#region 知识点二 代码实现
//学习希尔排序的前提条件
//先掌握插入排序
//希尔排序实例
//实现升序排序 8 7 1 5 4 2 6 3 9 把大的元素放在最后面
//创建无序数组
int[] array = new int[] { 8, 7, 1, 5, 4, 2, 6, 3, 9 };
//希尔排序核心代码
//第一步：实现插入排序
////第一层循环 是用来取出未排序区中的元素的
//for (int i = 1; i < array.Length; i++)
//{
// //得出未排序区的元素
// int nowSortNum = array[i];
// //得出排序区中最后一个元素索引
// int sortIndex = i - 1;
// //进入条件
// //首先排序区中还有可以比较的 >=0
// //排序区中元素 满足交换条件 升序就是排序区中元素要大于未排序区中元素
// while (sortIndex >= 0 &&
// array[sortIndex] > nowSortNum)
// {
// array[sortIndex + 1] = array[sortIndex];
// --sortIndex;
// }
// //找到位置过后 真正的插入 值
// array[sortIndex + 1] = nowSortNum;
//}
////打印输出
//for (int i = 0; i < array.Length; i++)
//{
// Console.WriteLine(array[i]);
//}
//第二步：确定步长
//基本规则：每次步长变化都是/2
//一开始步长 就是数组的长度/2
//之后每一次 都是在上一次的步长基础上/2
//结束条件是 步长 <=0
//1.第一次的步长是数组长度/2 所以：int step = array.length/2
//2.之后每一次步长变化都是/2 索引：step /= 2
//3.最小步长是1 所以：step > 0
for (int step = array.Length / 2; step > 0; step /= 2)
{
//注意：每次得到步长后 会把该步长下所有序列都进行插入排序
//第三步：执行插入排序
//i=1代码 相当于 代表取出来的未排序区的第一个元素
//for (int i = 1; i < array.Length; i++)
//i=step 相当于 代表取出来的未排序区的第一个元素
for (int i = step; i < array.Length; i++)
{
//得出未排序区的元素
int nowSortNum = array[i];
//得出排序区中最后一个元素索引
//int sortIndex = i - 1;
//i-step 代表和子序列中 已排序区元素一一比较
int sortIndex = i - step;
//进入条件
//首先排序区中还有可以比较的 >=0
//排序区中元素 满足交换条件 升序就是排序区中元素要大于未排序区中元素
while (sortIndex >= 0 &&
array[sortIndex] > nowSortNum)
{
//+1代表当前比较的对象往后移1个位置 代表整个序列中的下一个位置
//array[sortIndex + 1] = array[sortIndex];
//+step代表当前比较的对象往后移步长个位置 代表子序列中的下一个位置
array[sortIndex + step] = array[sortIndex];
//往前移一个单位 准备下次的比较
//--sortIndex;
//往前移一个步长单位 准备下次的比较
sortIndex -= step;
}
//找到位置过后 往前一个位置的插入值
//array[sortIndex + 1] = nowSortNum;
//找到位置过后 往前一个步长位置的插入值
array[sortIndex + step] = nowSortNum;
}
}
//打印输出
for (int i = 0; i < array.Length; i++)
{
Console.WriteLine(array[i]);
//1
//2
//3
//4
//5
//6
//7
//8
//9
}
#endregion
#region 知识点三 总结
//基本原理
//设置步长
//步长不停缩小
//到1排序后结束
//具体排序方式
//插入排序原理
//套路写法
//三层循环
//一层获取步长
//一层获取未排序区元素
//一层找到合适位置插入
//注意事项
//步长确定后
//会将所有子序列进行插入排序
#endregion
}
}
}
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 785293209@qq.com
