希尔排序

测试代码如下。

/**
    @hushunfeng
    希尔排序
    从小到大排列
*/
#include<stdio.h>


//单次希尔排序，即一次直接插入排序
//array为需要排序的数组
//dk为希尔排序算法中的增量
void shellInsert(int *array,int dk) {
    //---
    int i;
    int j;
    int arraySize = 10;
    for(i=0;(i+dk)<arraySize;i++) {
        //待插入的数据进行缓存
        int temp = array[i+dk];
        for(j=i;j>=0;j-=dk) {
            if(array[j+dk]<array[j]) {
                array[j+dk] = array[j];
            }
            else
                break;
        }
        //将temp的值放到腾空出来的位置中
        array[j+dk] = temp;
    }
}

//iArray为增量序列数组
void shellSort(int *array) {

    int i;
    int iArraySize = 5;

    int iArray[] = {9,5,3,2,1};
    for(i=0;i<iArraySize;i++) {
        shellInsert(array,iArray[i]);
    }
    
}

//main
void main() {
    int i;
    int array[] = {49,38,65,97,76,13,27,49,55,04};
    int arraySize = 10;
    //---
    shellSort(array);
    //排序后输出
    for(i=0;i<arraySize;i++) {
        printf("%d
",array[i]);
    }
}

希尔排序：需要经过好几轮的插入排序，每轮选取一个增量△。