C#排序算法之希尔排序

希尔排序.gif

1. 希尔排序，也叫缩小增量排序，是直接插入排序算法的一种更高效的版本，适合中级数量级的排序，属于非稳定排序算法。

2. 原理：以升序为例，该方法实质上是分组插入排序，比较相隔较远距离（称为[增量]的数，使得数移动时能跨过多个元素，则进行一次比较就可能消除多个元素交换。思考一下，直接插入排序是什么时候最高效呢，1.数据量少。2.数据数组有序。而希尔排序可以提前将局部数组变得有序，减少了数据移动的步骤。

3. 思路：在数组中[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