常见排序（2）

常见排序（2）

二：希尔排序（排升序）：

（1）排序思想：

希尔排序可以看作是在直接插入排序上的改进，希尔排序为多次 预排序+直接排序。

给出一数组a[10] = {6,1,2,7,9,3,4,5,10,8}; 假设给定一定的间距gap=3.把数据按照间距进行分割。

上图：我们可以看出数组按照gap 分成了3组，把三组分别进行排序，排序方法为直接插入排序。

排序第一次：

我们可以清楚的看到，排序的数组相对于之间的数组，小的尽可能的在前面，大的在后面。在这里，我们在完成预排序，使数组相对有序一些，然而序排还未完成。

gap=3的间距太大，排序不能完成，我们就再次改变gap的间距，这次gap=2。

如图所示，我们把数组分成了两组，我们再对它进行预排序，排序的方法为直接插入排序。

gap=2时的第一次排序。

这次，我们可以更加直观的看出，小的数字在前，大的在后。

 当gap=2时的排序结束后，我们的预排序就结束了。直接插入排序。直接插入排序就相当于是gap=1时的预排序，两者相同。

排序的思想就到这里结束。

（2）代码难点：

1>如何使gap逐渐减少，直到减为1。通常我们的处理方法为int gap=n(n为数组的大小),  gap=gap/2;因为当gap无论为奇数还是偶数时，都可以取到1，是直接插入排序可以继续。

2>我们在排序的过程中一直在使用直接插入排序，那么我们知道在直接插入排序中有一个end的变量，那么在希尔排序中，我们的end为多少呢？gap=3为例：

我们可以从图中看出每次的gap组的end 位不会超过紫色的end位，紫色的end位为最终的end位，而这个位置正好是int end=n-gap位 。

代码如下：