希爾排序，也叫縮小增量排序，是直接插入排序算法的一種更高效的版本，適合中級(jí)數(shù)量級(jí)的排序，屬于非穩(wěn)定排序算法。
原理：以升序?yàn)槔?/strong>，該方法實(shí)質(zhì)上是分組插入排序，比較相隔較遠(yuǎn)距離（稱為[增量]的數(shù)，使得數(shù)移動(dòng)時(shí)能跨過多個(gè)元素，則進(jìn)行一次比較就可能消除多個(gè)元素交換。思考一下，直接插入排序是什么時(shí)候最高效呢，1.數(shù)據(jù)量少。2.數(shù)據(jù)數(shù)組有序。而希爾排序可以提前將局部數(shù)組變得有序，減少了數(shù)據(jù)移動(dòng)的步驟。
思路：在數(shù)組中[8,9,1,7,2,3,5,4,6,0]，選取增量為5的數(shù)據(jù)進(jìn)行比較，第二次增量為2，第三次增量為1，以此類推。
以數(shù)組[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）要排序的數(shù)組是：[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 }; //待排序數(shù)組
//int[] array = { 9, 1, 2, 5, 7, 4, 8, 6, 3, 5}; //待排序數(shù)組
//int[] array = { 592, 401, 874, 141, 348, 72, 911, 887, 820, 283 }; //待排序數(shù)組
//int[] array = { 61, 109, 149, 111, 34, 2, 24, 119, 122, 125, 27, 145}; //待排序數(shù)組
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("希爾排序后的數(shù)列：");
foreach (int item in array)
Console.Write(item + " ");
Console.WriteLine();
}
//控制臺(tái)遍歷輸出
Console.ReadLine();
}
/// <summary>
/// 希爾排序
/// </summary>
/// <param name="array">要排序的數(shù)列</param>
/// <param name="gap"> 要進(jìn)行比較的數(shù)列間隔</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.輸出結(jié)果
增量:6
希爾排序后的數(shù)列：
14 22 35 1 16 25 15 23 68 9 33 33 15
增量:3
希爾排序后的數(shù)列：
1 16 25 9 22 33 14 23 35 15 33 68 15
增量:1
希爾排序后的數(shù)列：
1 9 14 15 15 16 22 23 25 33 33 35 68
