C#排序算法——希尔排序

vlambda
2020-10-07

C#排序算法——希尔排序

This browser does not support music or audio playback. Please play it in Weixin or another browser.

有一个早晨我扔掉了所有的昨天，从此我的脚步就轻盈了——泰戈尔《烧毁记忆》

“定义:将待排序数据按下标的一定增量分组，对每组使用直接插入排序算法。随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分为一组，算法便终止。希尔排序又称“缩小增量排序”，即每趟只对相同增量距离的关键字进行比较，这与关键字序列初始有序或无序无关。”

——前言：

希尔排序可以说是的加强版。既然是加强版效率肯定比插入排序要高。因为希尔排序首先会对待排数据进行跳跃分割成组，将数据进行一个基本排序。举个例子6,2,8,1有4个数，首先取增量2/1，这时8与6比较，6<8不需要换，再就是2与1比较，2>1调换位置。一个轮回后缩小增量为4/1，变为了插入排序。最后一次排序时，整个序列已经做到基本有序，这时只需要作出少量比较和移动。

动图演示：

C#排序算法——希尔排序

静图演示：

—

Code

下面使用C#代码进行实现：

/// <summary>/// 希尔排序 从小到大/// </summary>private void XiErSore(List<int> Nums){ //增量从一半开始，慢慢缩减，最小至为1 for (int AddCount = Nums.Count / 2; AddCount > 0; AddCount /= 2) { //从增量开始，逐个对其所在组进行插入排序 for (int i = AddCount; i < Nums.Count; i++) { int j = i - AddCount; while (j >= 0 && Nums[j] > Nums[j + AddCount]) { Swap(Nums, j, j + AddCount); j -= AddCount; } } }}/// <summary>/// 交换数据/// </summary>private void Swap(List<int> Nums, int index1, int index2){ int temp = Nums[index1]; Nums[index1] = Nums[index2]; Nums[index2] = temp;}