C#希尔排序算法

前言

希尔排序简单的来说就是一种改进的插入排序算法，它通过将待排序的元素分成若干个子序列，然后对每个子序列进行插入排序，最终逐步缩小子序列的间隔，直到整个序列变得有序。希尔排序的主要思想是通过插入排序的优势，减小逆序对的距离，从而提高排序效率。

希尔排序实现原理

首先要确定一个增量序列（初始间隔），将待排序序列分成多个子序列。 对每个子序列分别进行插入排序，即在子序列内部进行排序。 逐步减小增量，重复步骤2，直到增量为1，即完成最后一次插入排序，排序完成。

希尔排序动态图解

希尔排序代码实现

 ????????  public? static? void? ShellSort(  int[]?array)
????????{
???????????? int?arrLength?=?array.Length;

???????????? //?初始化增量（初始间隔）为数组长度的一半
???????????? int?gap?=?arrLength?/? 2;

???????????? //?不断缩小增量，直到增量为1
???????????? while?(gap?>? 0)
????????????{
???????????????? //?对每个子序列进行插入排序
???????????????? for?( int?i?=?gap;?i?<?arrLength;?i++)
????????????????{
???????????????????? int?temp?=?array[i];
???????????????????? int?j?=?i;

???????????????????? //?在子序列内部进行插入排序
???????????????????? while?(j?>=?gap?&&?array[j?-?gap]?>?temp)
????????????????????{
????????????????????????array[j]?=?array[j?-?gap];
????????????????????????j?-=?gap;
????????????????????}

????????????????????array[j]?=?temp;
????????????????}

???????????????? //?缩小增量
????????????????gap?/=? 2;
????????????}
????????}

????????  public? static? void? ShellSortRun( )
????????{
???????????? int[]?array?=?{? 19,? 20,? 22,? 32,? 34,? 50,? 99,? 49,? 1,? 11,? 11,? 55,? 35,? 93,? 96,? 71,? 70,? 38,? 78,? 48?};

????????????Console.WriteLine( "排序前数组："?+? string.Join( ",?",?array));

????????????ShellSort(array);

????????????Console.WriteLine( "排序后数组："?+? string.Join( ",?",?array));
????????}
                                                         

运行结果

参考文章

排序算法图解： https://cloud.tencent测试数据/developer/article/1502452

查看更多关于C#希尔排序算法的详细内容...