排序算法 之 希尔排序

原文地址http://www.cnblogs.com/liukemng/p/3723976.html

希尔排序是由D.L.Shell于1959年提出的，所以称为希尔排序。希尔排序又称缩小增量排序，是插入排序的一种改进。

基本思想：希尔排序是基于插入排序的以下特点：待排序的序列元素数量越少排序速度越快；待排序序列的元素基本有序时排序速度越快；基于以上思想将待排序序列分为多个子序列分别进行插入排序，然后减少子序列的个数重新进行插入排序，重复以上过程，直至待排序的序列只有一个再进行一次插入排序，则排序完成序列有序。

代码实现：

/// <summary>/// 希尔排序/// </summary>/// <param name="intArray"></param>/// <param name="length"></param>public static void ShellSort(int[] intArray, int length){    int gap, i, j, temp;    for (gap = length / 2; gap >= 1; gap = gap / 3+1)    {        for(i=gap;i<length;i++)        {            temp=intArray[i];            for(j=i-gap;j>=0&&intArray[j]>temp;j-=gap)                intArray[j+gap]=intArray[j];            intArray[j+gap]=temp;        }        if(gap==1)            break;    }}
需说明的是不同的间隔gap选择会对排序的效率有不同的影响，且不容易确定最佳的间隔gap，感兴趣的朋友可以搜索相关资料作为参考。
以上就是希尔排序的内容。