【数据结构】shell 排序

1、shell排序

---

按照某种增量序列，依次操作。在处理第i个增量d时，把整个待排数组Array中，距离为d的倍数的那些记录放在同一组（作为子序列），组内进行插入排序（也可以采用其他排序方式，不过试验证明插入排序效果最好）；逐渐扩大小序列的规模，而减少小序列个数，最后所有序列都合并在一个大序列中进行一趟插入排序，从而完成排序。注意，最后一个增量并不一定是1，可以让最后一个增量是比较小的数，然后对整个数列进行一次插入排序（因为此时已经基本有序）。与交换排序不同的是，shell排序不是着眼于相邻的记录来进行比较，而是对那些不相邻的记录进行比较和交换。

ps:

插入排序：直接插入排序（Straight Insertion Sorting）的基本思想是：把n个待排序的元素看成为一个有序表和一个无序表，开始时有序表中只包含一个元素，无序表中包含有n-1个元素，排序过程中每次从无序表中取出第一个元素，将它插入到有序表中的适当位置，使之成为新的有序表，重复n-1次可完成排序过程。

2、shell排序代码

---

void shellsort(int v[], int n) //按递增顺序排序
{
    int gap,i,j,temp;
    for(gap = n/2;gap > 0;gap /=2) //gap值也可以有其他取法
    {
        for(i=gap;i           for(j=i-gap;j>0 && v[j]>v[j+gap];j-=gap)
           {
               temp=v[j];
               v[j]=v[j+gap];
               v[j+gap]=temp;
           }
}