排序算法系列之希尔排序(4)

希尔排序

1. 希尔排序的巧妙之处在于把原数组拆分成 d 个子数组,其中 d 为间隔增量,使得间隔的数据之间也可以进行排序;
2. 对每个子数组进行插入排序;
3. 初期 d 为原数组length/2;每轮子数组都排序完毕以后, 间隔增量 d 继续除以2,继续分割子数组进行排序;
4. 直到 d &＃61; 1的时候,也就是最后一次排序,循环结束;之前增量 d !&＃61; 1 的间隔数组排序都是采用简单的插入排序算法;
5. 希尔排序主要拆分为2部分,首先最重要的部分是对增量的更改

   ///

   /// 希尔排序:使用增量分割子数组,使得间隔的数据可以进行插入排序,直到增量递减为1,进行最后一次排序///

   public void ShellSort(T[] datas) where T:IComparable{if (datas &＃61;&＃61; null) return;// 初始增量为数组长度的一半int gap &＃61; datas.Length / 2;while (gap >&＃61; 1){// 把距离为 gap 的元素编为一个组&＃xff0c;扫描所有组
   SellInsert(datas,gap);// 缩小增量到1为止gap /&＃61; 2;}}
6. 其次是对每次的子数组依次进行插入排序

   ///

   /// Shell希尔排序中的子数组直接插入排序 ///

   /// 未排序的无序数组/// 分隔增量private void SellInsert(T[] datas, int gap) where T :IComparable{if(datas &＃61;&＃61; null) return;for (int i &＃61; gap, j; i ){T tampData &＃61; datas[i];// 对距离为 gap 的子数据组进行简单插入排序for (j &＃61; i - gap; j >&＃61; 0 && tampData.CompareTo(datas[j]) <0; j -&＃61; gap){// 数据左右下标交换,把大数据挪到子数组的右边datas[j &＃43; gap] &＃61; datas[j];}if (j !&＃61; i - gap){// 子数据插入左端最适合的位置进行复制datas[j &＃43; gap] &＃61; tampData;}}}
7. 测试数据:

   string[] ShellDatas &＃61; { "a", "e", "f", "z", "G", "A", "b", "d", "F", "b", "B" };program.ShellSort(ShellDatas);DebugExtension.DebugArray(ShellDatas);

8. 测试结果