top
友情提示
测试消息
确定
友情提示

处理中,请稍后...

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

希尔排序基本思想:把待排序的数据元素分为若干个组,对同一个小组内的数据元素运用直接插入排序;小组的个数逐渐减少;当完成了所有元素都在一个组内的排序后,排序过程结束。【其实最后就是进行了一个增量为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)²)
 
标签
ShellSort
希尔排序
算法
插入排序
缩小增量排序
上一篇:排序算法:插入排序之直接插入排序
下一篇:排序算法:选择排序之直接选择排序
文章阅读完了, 快到评论区留下你的看法吧!
Email:
验证码:
昵 称 :
评论列表
热门标签
今日倒计时
小时 分钟
年少不识曲中意,再听已是曲中人
加油吧骚年
文章分类
最新文章
浏览排行
分享

关于友情链接

友情链接申请请到留言板块留言。注明网站名称及网址。期待您的友链,欢迎留言。
最新留言
[2018/04/07]太难找了,找到了
[2018/03/20]Entry fileTemplates//Singleton.java.ft not found in C:/Dev/android-studio/lib/resources_en.jar 该错误对我们使用AS没有影响吗?为什么复制保存后重新创建一个新的之后这个错误又出现了?
[2018/01/23]815cce30b85eb6b7ee7930c09135fcf7好漂亮的博客空间啊
[2018/01/06]好漂亮的博客.......
[2017/12/26]试试水
[2017/12/20] 博主可以分享一下这个源码不, 很喜欢这个博客
[2017/11/19]你加我友链了????
[2017/11/19]你的alert 很不友好哈
[2017/11/19]友链已添加
[2017/11/19]路过帮踩。
Copyright © 2018 DevSONG . All rights reserved. 有疑问或者建议? 留言给我或者E-mail me
滇ICP备17002307号-3