代码 #include < stdio.h > #include < stdlib.h > int initialStep( int size); void sort( int array[], int from, int end); void insertSort( int array[], int groupIndex, int step, int end); void move( int array[], int startIndex, int endIndex, int step); void PrintArray( const char * strMsg, int array[], int nLength); int main( int argc, char * argv[]){ int data[ 13 ] = { 8 , 5 , 4 , 6 , 13 , 7 , 1 , 9 , 12 , 11 , 3 , 10 , 2 }; sort(data, 0 , 12 ); PrintArray( " Shell Sort: " ,data, 13 ); system( " PAUSE " ); return 0 ;} /* * * 根据数组长度求初始步长 * * 我们选择步长的公式为：2^k-1,2^(k-1)-1,...,15,7,3,1 ，其中2^k 减一即为该步长序列，k * 为排序轮次 * * 初始步长：step = 2^k-1 * 初始步长约束条件：step < len - 1 初始步长的值要小于数组长度还要减一的值（因 * 为第一轮分组时尽量不要分为一组，除非数组本身的长度就小于等于4） * * 由上面两个关系试可以得知：2^k - 1 < len - 1 关系式，其中k为轮次，如果把 2^k 表 达式 * 转换成 step 表达式，则 2^k-1 可使用 (step + 1)*2-1 替换（因为 step+1 相当于第k-1 * 轮的步长，所以在 step+1 基础上乘以 2 就相当于 2^k 了），即步长与数组长度的关系不等式为 * (step + 1)*2 - 1 < len -1 * * @param len 数组长度 * @return */ int initialStep( int size) { /* * 初始值设置为步长公式中的最小步长，从最小步长推导出最长初始步长值，即按照以下公式来推: * 1,3,7,15,...,2^(k-1)-1,2^k-1 * 如果数组长度小于等于4时，步长为1，即长度小于等于4的数组不且分组，此时直接退化为直接插 * 入排序 */ int step = 1 ; // 试探下一个步长是否满足条件，如果满足条件，则步长置为下一步长 while ((step + 1 ) * 2 - 1 < size - 1 ) { step = (step + 1 ) * 2 - 1 ; } printf( " 初始步长 - %d\n " ,step); return step; } /* * * 排序算法的实现，对数组中指定的元素进行排序 * @param array 待排序的数组 * @param from 从哪里开始排序 * @param end 排到哪里 * @param c 比较器 */ void sort( int array[], int from, int end) { int groupIndex; // 初始步长，实质为每轮的分组数 int step = initialStep(end - from + 1 ); // 第一层循环是对排序轮次进行循环。(step + 1) / 2 - 1 为下一轮步长值 for (; step >= 1 ; step = (step + 1 ) / 2 - 1 ) { // 对每轮里的每个分组进行循环 for (groupIndex = 0 ; groupIndex < step; groupIndex ++ ) { // 对每组进行直接插入排序 insertSort(array, groupIndex, step, end); } } } /* * * 直接插入排序实现 * @param array 待排序数组 * @param groupIndex 对每轮的哪一组进行排序 * @param step 步长 * @param end 整个数组要排哪个元素止 * @param c 比较器 */ void insertSort( int array[], int groupIndex, int step, int end) { int i,j; int startIndex = groupIndex; // 从哪里开始排序 int endIndex = startIndex; // 排到哪里 /* * 排到哪里需要计算得到，从开始排序元素开始，以step步长，可求得下一元素是否在数组范围内， * 如果在数组范围内，则继续循环，直到索引超现数组范围 */ while ((endIndex + step) <= end) { endIndex += step; } // i为每小组里的第二个元素开始 for (i = groupIndex + step; i <= end; i += step) { for (j = groupIndex; j < i; j += step) { int insertedElem = array[i]; // 从有序数组中最一个元素开始查找第一个大于待插入的元素 if (array[j] >= insertedElem) { // 找到插入点后，从插入点开始向后所有元素后移一位 move(array, j, i - step, step); array[j] = insertedElem; break ; } } } } /* * * 以指定的步长将数组元素后移，步长指定每个元素间的间隔 * @param array 待排序数组 * @param startIndex 从哪里开始移 * @param endIndex 到哪个元素止 * @param step 步长 */ void move( int array[], int startIndex, int endIndex, int step) { int i; for (i = endIndex; i >= startIndex; i -= step) { array[i + step] = array[i]; } } void PrintArray( const char * strMsg, int array[], int nLength){ int i; printf( " %s " ,strMsg); for (i = 0 ;i < nLength;i ++ ) { printf( " %d " ,array[i]); } printf( " \n " );}
以上代码主要修改自：http://www.javaeye.com/topic/547734 http://www.javaeye.com/topic/547735其它参考资料：http://www.cnblogs.com/ziyifly/archive/2008/09/10/1288499.htmlhttp://www.java2000.net/p11750http://mintelong.javaeye.com/blog/467833http://student.zjzk.cn/course_ware/data_structure/web/paixu/paixu8.2.2.1.htmhttp://www.cnblogs.com/hualei/archive/2010/08/17/1801850.html
转载于:https://www.cnblogs.com/feima-lxl/archive/2010/08/19/1802902.html
相关资源：数据结构—成绩单生成器