前言

希尔排序是插入排序的优化，它利用了分治的思想，将需要排序的数组分为几段，在每一段中做插入排序。通过分治的思想，使得排序效率比起原来的插入排序要快了很多。对于插入排序，不了解的可以查看我之前的文章（C#排序算法之插入，选择和冒泡排序）。

算法思路

希尔排序分段的思路一般是有一个步长，数组内的元素按照步长划分为几部分，在这几部分中做插入排序，然后再缩短步长，最后步长为一时就是对全数组的插入排序，因为前面的分段插入排序过程中，数组从无序逐步变成有序，所以最后一次插入排序只需要移动极少部分元素，这比起直接对整个数组做插入排序要快了很多。步长和每次步长的变化都是可以自己定义，不过一般都是将初始步长设置为数组元素一般，然后每次步长缩小一半，这种设置方式常见而且效率很高。

例如：有一组数据5，1，1，3，2，10，8。假设初始步长为数据长度一半，即3。每次步长缩小一半。

首次步长为3，可以将数组分为以下三部分

5，3，8

1，2

1，10

对其进行插入排序得到结果

3，1，1，5，2，10，8

步长缩小，此时步长为1，可将数组分为1部分，并对齐进行插入排序，得到结果为

1，1，2，3，5，8，10

例子中的数据量比较少，不能很好的体现出和插入的区别，但是数据量一旦大起来，每一次分段进行插入排序需要移动的数据都会大大减少，效率也会高非常多。

实现代码

Sort父类中仅仅包含一个数据元素交换方法Swap。

public class ShellSort : Sort{public static void Sort(int[] array){int step = array.Length / 2;while (step > 0){for (int i = step; i < array.Length; i++){int index = i;for (int j = i - step; j >= 0; j-=step){if (array[i] >= array[j])break;index = j;}int val = array[i];for (int j = i; j > index; j -= step)array[j] = array[j - step];array[index] = val;}step /= 2;}}}