希尔排序.gif
希尔排序，也叫缩小增量排序，是直接插入排序算法的一种更高效的版本，适合中级数量级的排序，属于非稳定排序算法。
原理：以升序为例，该方法实质上是分组插入排序，比较相隔较远距离（称为[增量]的数，使得数移动时能跨过多个元素，则进行一次比较就可能消除多个元素交换。思考一下，直接插入排序是什么时候最高效呢，1.数据量少。2.数据数组有序。而希尔排序可以提前将局部数组变得有序，减少了数据移动的步骤。
思路：在数组中[8,9,1,7,2,3,5,4,6,0]，选取增量为5的数据进行比较，第二次增量为2，第三次增量为1，以此类推。
以数组[8,9,1,7,2,3,5,4,6,0]为例：
第1次排序：[3,5,1,6,0,8,9,4,7,2]
第2次排序：[0,2,1,4,3,5,7,6,9,8]
第3次排序：[0,1,2,3,4,5,6,7,8,9]
4.举例：
（1）要排序的数组是：[15, 22, 35, 9, 16, 33, 15, 23, 68, 1, 33, 25, 14]。
//希尔排序是直接排序算法的一种变形，比直接排序算法灵活。
static void Main(string[] args)
{
int[] array = { 15, 22, 35, 9, 16, 33, 15, 23, 68, 1, 33, 25, 14 }; //待排序数组
//int[] array = { 9, 1, 2, 5, 7, 4, 8, 6, 3, 5}; //待排序数组
//int[] array = { 592, 401, 874, 141, 348, 72, 911, 887, 820, 283 }; //待排序数组
//int[] array = { 61, 109, 149, 111, 34, 2, 24, 119, 122, 125, 27, 145}; //待排序数组
int gap = array.Length / 2;
while (gap > 0)
{
Console.WriteLine(gap);
//ShellSort_1(array, gap, array.Length);
ShellSort(array, gap);
gap = gap / 2;
Console.WriteLine("希尔排序后的数列：");
foreach (int item in array)
Console.Write(item + " ");
Console.WriteLine();
}
//控制台遍历输出
Console.ReadLine();
}
/// <summary>
/// 希尔排序
/// </summary>
/// <param name="array">要排序的数列</param>
/// <param name="gap"> 要进行比较的数列间隔</param>
static void ShellSort(int[]array,int gap)
{
for(int i = 0;i < array.Length-gap; i++)
{
if(array[i]>array[i + gap])
{
int temp = array[i];
array[i] = array[i + gap];
array[i + gap] = temp;
int j;
j = i;
do
{
if (j - gap < 0) break;
if (array[j] >= array[j - gap])
{
break;
}
else
{
int temp1 = array[j];
array[j] = array[j - gap];
array[j - gap] = temp1;
}
j = j - gap;
}
while (j > 0);
}
}
}
5.输出结果
增量:6
希尔排序后的数列：
14 22 35 1 16 25 15 23 68 9 33 33 15
增量:3
希尔排序后的数列：
1 16 25 9 22 33 14 23 35 15 33 68 15
增量:1
希尔排序后的数列：
1 9 14 15 15 16 22 23 25 33 33 35 68
