排序算法:插入排序之希尔排序
希尔排序是插入排序之一,可以说其是直接插入排序的一个进一步实现,在其中你会发现直接插入排序的存在。

希尔排序基本思想:把待排序的数据元素分为若干个组,对同一个小组内的数据元素运用直接插入排序;小组的个数逐渐减少;当完成了所有元素都在一个组内的排序后,排序过程结束。【其实最后就是进行了一个增量为1的直接插入排序,只不此时集合元素顺序已经快接近排序完成的状态,也就是直接插入排序运行效率较高的状态】。由于每一次分组数都是减少的,即过程中直接插入排序的增量是减少的,所以希尔排序又称缩小增量排序。

C语言实现及测试
#include <stdio.h>

/**
 * 希尔排序:升序
 * @param data       待排序集合
 * @param len        待排序集合长度
 * @param group      分组数据, 最后一个元素必须为 1
 * @param numofGroup 分组数据个数
 *
 * 注:(1) 分组数据最后一个元素必须为 1, 也就是分组长度为 1, 只有进行了一个增量为 1 的直接插入排序, 才能保证集合完成排序,
 *     否则集合只是区域性有序,只有极少的特殊情况碰巧有序,这得看原始数据。
 *     
 *     (2) 此处为方便演示,依旧只是进行简单的 int数组 排序
 */
void ShellSortAsc(int data[], int len, int group[], int numofGroup){
    int i = 0, j = 0, k = 0, m = 0, span = 0;
    int temp = 0;

    for(m = 0; m < numofGroup; m++){ //numofGroup 个增量
        span = group[m];
        for(k = 0; k < span; k++){ //每个分组数据都对应各自的组数, span 即为组数
            //熟悉的直接插入排序登场,不过注意增量不再是 1, 而是span
            for(i = k; i < len - span; i += span){
                temp = data[i + span];
                j = i;
                while(j > -1 && temp < data[j]){  //升降序决定
                    data[j + span] = data[j];
                    j -= span;
                }
                data[j + span] = temp;
            }

        }
    }
}

/**
 * 测试
 */
int main(int argc, char const *argv[]){
    
    int i = 0;
    int a[] = {65, 34, 25, 87, 12, 38, 56, 46, 14, 77, 92, 23};
    int n = 12;
    int group[] = {6, 3, 1};  //分组数据
    int numofGroup = 3; //分组集合长度
    ShellSortAsc(a, n, group, numofGroup);

    for(i = 0; i < n; i++){
        printf("%d ", a[i]);
    }

    return 0;
}

上述排序过程图解:
文章正文图片

总结
比较希尔排序和直接插入排序,直接插入排序是两重循环,希尔排序是四重循环,但是分析希尔排序的实现步骤你会发现,外面两重循环的次数很小,并且随着增量的减小,小组元素个数变多时,组内的成员已经基本有序,这样每次直接插入排序运行的时间效率就会提高。所以,希尔排序时间复杂度相较于直接插入排序而言改善了不少。若增量的取值比较合理,则其时间复杂度为O(n(lbn)²)
 
It's
欢迎访问本站,欢迎留言、分享、点赞。愿您阅读愉快!
*转载请注明出处,严禁非法转载。
https://www.devsong.org
QQ留言 邮箱留言
头像
引用:
取消回复
提交
涂鸦
涂鸦
热门