C# 希爾排序 實現代碼

 

 
using System;using System.Collections.Generic;using System.Linq;using System.Text;namespace Sort{    class ShellSorter    {        public static int[] Sort(int[] a)        {            ShellSort(a);            return  a;        }        public static void ShellSort(int[] myArray)        {            int i, j, increment;            int temp;            for (increment = myArray.Length / 2; increment > 0; increment /= 2)            {                for (i = increment; i < myArray.Length; i++)                {                    temp = myArray[i];                    for (j = i; j >= increment; j -= increment)                    {                        if (temp < myArray[j - increment])                            myArray[j] = myArray[j - increment];                        else                            break;                    }                    myArray[j] = temp;                }            }        }    }}
 

希爾排序是對直接插入排序算法的改進，其主要思想是：先將整個排序數列分割成為若干個子序列，在子序列分別進行直接插入排序，待整個數列基本有序時再對全部進行一次直接插入排序。以此來形成新的有序數列。一般分割方法是兩個元素相距d=n/2,n/4,n/8……以此類推。 1.基本思想： 把整個待排序的數據元素分成若干個小組，對同一小組內的數據元素用直接插入法排序；小組的個數逐次縮小，當完成了所有數據元素都在一個組內的排序後排序過程結束。 2.技巧： 小組的構成不是簡單地“逐段分割”，而是將相隔某個增量dk的記錄組成一個小組,讓增量dk逐趟縮短（例如依次取5,3,1），直到dk＝1為止。 3.優點： 讓關鍵字值小的元素能很快前移，且序列若基本有序時，再用直接插入排序處理，時間效率會高很多。 例子來源 例子來源        流程圖來源

對於插入排序算法來說，如果原來的數據就是有序的，那麼數據就不需要移動，而插入排序算法的效率主要消耗在數據的移動中。因此可知：如果數據的本身就是有序的或者本身基本有序，那麼效率就會得到提高