Shell排序算法

gistfile1.c

/**
*Shell 排序算法是D.L Shell于1959年发明的，基本思想：先比较距离远的元素，
而不是像简单交换排序算法那样先比较相邻的元素，这样可以减少大量的无序情况，
从而减轻后续工作。被比较的元素之间的距离逐渐减少，直到减到1，
这时候的排序变成相邻元素的交换。
shellsort函数：按递增顺序对v[0]...v[n]进行排序
*/
void shell_sort(int v[],int n){
     
     int gap, i, j, temp;
     
     for(gap = n/2; gap >0 ;gap /= 2){   //gap的值从开始的n/2,n/4....2,1
          for(i=gap; i<n; i++)           //从v[gap],v[gap+1]....v[n]排序
              for(j=i-gap; j>=0&&v[j]>v[j+gap]; j-=gap){   //j-=gap保证从v[i]端下来的较小的数据继续向前罗列
                   temp = v[j];
                   v[j] = v[j+gap];
                   v[j+gap] = temp; 
        }
   }
}

/** Shell 排序是不稳定的，较直接插入排序有较大的改进，Shell的平均比较次数和平均移动次数都是n^1.3左右;
    直接插入排序最好的时间复杂度是o(n),最坏时间复杂度是o(n^2)*/