希尔排序(shell)理论---不含源码

　　希尔排序，是一个缩小增量排序。它根据步长来进行排序，步长不同可能会产生不同的序列，但是他们的最终结果是相同的，希尔排序的官方理论难以理解，这里就用非官方的解释来阐述。

　　原理：

　　　　>1.加入有n个节点的序列，假设希尔排序的步长i，那么我们第一步就是将这n个节点，每隔i个座位为一组，如下所示（步长i要取好）：

　　　　　　[n_1,n_1+i]

　　　　　　[n₂, n_i+2]

　　　　　　[...........]

　　　　　　[n_x, n_n]

　　　　>2.然后每一组两两比较，如n₁和n_1+i比较，选择合适（合适是指排序的升降关系）的数据排在前面。假如n_1+i < n₁,且按升序排，那么第一组排序后的序列为[n_1+i, n₁],其他的依次类推，组成排好序的x组。假设如下是排好的序列。

　　　　　　[n_1+i,n₁]

　　　　　　[n₂, n_i+2]

　　　　　　[n₃, n_i+3]

　　　　　　[n_i+4, n₄]

　　　　　　[...........]

　　　　　　[n_x, n_n]

　　　　>3.最后将按纵向的序列，将所有的节点依次写好，这就是希尔排序的第一趟的结果了，根据>2.来的结果是：n_1+i, n₂, n₃, n_i+4, ...., n_x, n₁, n_i+2, n_i+3, n₄, ...., n_n

　　　　>4.然后将步长i减去1，重复上面的操作，直到i=0，结束。

示例：以(5，6，1，8，4，9)序列为例，演示第一趟排序的结果

巴特西