希尔排序的C语言实现（1）

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› C++›C++教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

代码

#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.html
http://www.java2000.net/p11750
http://mintelong.javaeye.com/blog/467833
http://student.zjzk.cn/course_ware/data_structure/web/paixu/paixu8.2.2.1.htm
http://www.cnblogs.com/hualei/archive/2010/08/17/1801850.html