鱼都会的希尔排序

最近看了一些网上的希尔排序的文字，感觉都有些跳节，说的不是很详细，甚至有错误的地方，让人迷惑。这样的话，鱼就没法学会希尔排序了。所以决定写一个比较详细希的尔排序算法的文章。

首先要了解希尔排序是什么。希尔排序法（缩小增量法）属于插入类排序，是将整个无序列分割为若干小的子序列分别进行排序的方法。

具体是怎么样做的呢？我们看看一下一个例子，有这样一组数据：

7 6  0  4 3  1  5 2  9  8

共10个数字，所以我们设置区间d为d=leng/2=5；就是将这10个数字分为两份，每份5个：

7 6  0  4 3  |  1 5  2  9  8

我们设前面为a1，后面为a2这样来描述。

首先a1中的第一位和a2中的第一位比较如果a1>a2就交换这两个数值，得到：

1 6  0  4 3  |  7  5 2  9  8

以此类推我们比较a1的第二位和a2的第二位得到：

1 5 0  4  3 |  7  6  2 9  8

然后我们将a1的最后一个比较完成，得到：

1  5 2  4  3 |  7  6 0  9  8               

然后我们进行将d再次缩小 d=d/2=2；得到：

1 5  |  2 4  |  3   7  |  6  0  |  9  8

— ——  ———   ————  ———   ————

 A1     A2        A3      A4       A5

这样我们就拥有了a1到a5的5个组；

然后我们让a1的第一个与a2的第一个比较，如果a1>a2就交换，可看到是不用交换的。我们得到：

1 5  |  2 4  |  3   7  |  6  0  |  9  8

然后我们在比较a1的第二个和a2的第二个，如果a1>a2就交换，所以我们得到：

1 4 |  2  5  |  3   7  |  6  0  |  9  8

现在我们a1与a2比较完成了，我们就要向后移动，开始以a2为基础比较，首先a2中的第一个与a3中的第一个比较，如果a2>a3就交换，可以看出并没有变化。得到：

1  4|  2  5 |  3   7  |  6  0  |  9  8

然后再比较a1中的第一个与a2中的第一个，也没有变化，因为这部分恰巧已经排好了。我们再让a2的第二个数值与a3的第二个数值比较，如果a2>a3就交换，但是恰巧又不用交换，得到：

1  4|  2  5 |  3   7  |  6  0  |  9  8

如上所诉，我们在进行a3的第二个与a4的第二个比较时发现a3>a4,所以我们交换了他们，得到：

1  4|  2  5 |  3   0  |  6  7  |  9  8

然后我们再让a2的第二个与a3的第二个比较，得出如下结果：

1  4|  2  0 |  3   5  |  6  7  |  9  8

最后让a1的第二个与a3的第二个比较，得出如下结果：

1  0 |  2  4 |  3   5 |  6  7  |  9  8

之后我们让a4与a5比较，以此类推，我们发现都无法交换，并且已经打到末尾。

这时我们将我们的d再次缩小d=d/2 =1；得到如下序列：

1  |  0  |  2  |  4  | 3  |  5 |  6  |  7 |  9  |  8

这时，我们就可以进行标准的插入排序了：

我们将这组数据分为a0~a9这样的10组；

然后使用上述的方法进行比较交换；

比如：

让a1与a2比较，如果a1>a2交换，得到：

0 |  1 | 2  |  4  |  3  |  5 |  6  |  7 |  9  |  8

然后发现我们达到了a1的最后一位，那么向下移动，让a2与a3比较，如果a2>a3，就交换他们，发现无法交换：

0 |  1  | 2  |  4 |  3  | 5  |  6 |  7  | 9  |  8

然后再让a1与a2比较，发现也无法交换：

0 |  1  | 2  |  4 |  3  | 5  |  6 |  7  | 9  |  8

这样就再次往下移动，让a3与a4比较，如果a3>a4就交换他们，得到：

0 |  1  | 2  |  3 |  4  | 5  |  6 |  7  | 9  |  8

以此类推，我们发现a8可以与a9交换，然后得到：

       0        |  1 |  2  | 4  |  3 |  5  | 6  |  7 |  8 | 9

这样我们发现已经达到末尾，这时需要再次缩小范围d=d/2=0；我们发现d已经是0了，无法再次缩小，所以结束循环，输出我们排列好的数据，得到：

0   1  2 3  4  5 6  7  8  9

看！是不是我们要的排序呢？很简单吧。那么代码怎么实现呢？如下：

static void ShellSort(int[] m_Array)

{

        int d = m_Array.Length / 2;

        while (d > 0)

        {

              for (int i = d; i < m_Array.Length; i++)

              {

                    for (int j = i - d; j >= 0; j -= d)// 每次移动一个组的长度

                    {

                         if (m_Array[j] > m_Array[j + d])

                         {

                                  int temp = m_Array[j];

                                  m_Array[j] = m_Array[j + d];

                                  m_Array[j + d] = temp;

                            }

                       }

                   }// end for

              d /= 2;

         }// end while

}