排序——希尔排序

简介: 排序——希尔排序

希尔排序(基于逐趟缩小增量)

基本思想

  • 先将整个待排记录序列分割成若干子序列,分别进行直接插入排序,待整个序列中的记录“基本有序”时,再对全体记录进行一次直接插入排序。

在这里插入图片描述

算法实现

void ShellSort(SqList &L, int dlta[], int t){
    // 按增量序列dlta[0…t-1]对顺序表L作Shell排序
    for(k = 0; k < t; k++)
        ShellInsert(L, dlta[k]);  // 增量为dlta[k]的一趟插入排序

}

void ShellInsert(SqList &L, int dk){
    // 对顺序表L进行一趟增量为dk的Shell排序,dk为步长因子
    for(i = dk + 1; i <= L.length; i++){
        // 开始将r[i] 插入有序增量子表
        if(r[i].key < r[i - dk].key){
            r[0] = r[i];  // 暂存在r[0]
            for(j = i - dk; j > 0 && (r[0].key < r[j].key); j = j - dk)
                r[j + dk] = r[j];  // 关键字较大的记录在子表中后移
            r[j + dk] = r[0];  // 在本趟结束时将r[i]插入到正确位置
        }
    }
}

算法分析

  • 时间复杂度: O(n3/2)  
  • 空间复杂度为 O(1)
  • 稳定性: 不稳定
如何选择最佳的序列,目前 尚未解决
最后一个增量值 必须为1,无除1以外的公因子
不宜在链式存储结构上实现
目录
相关文章
|
7月前
|
搜索推荐 算法 Shell
排序——插入排序
排序——插入排序
50 0
|
7月前
|
算法 搜索推荐
排序——选择排序
排序——选择排序
76 0
|
存储 搜索推荐 测试技术
排序篇(一)----插入排序
排序篇(一)----插入排序
52 0
|
算法 搜索推荐 索引
排序篇(二)----选择排序
排序篇(二)----选择排序
38 0
|
存储 搜索推荐 测试技术
排序(1)之插入排序
从今天小编就开始给大家介绍排序的内容,对于排序内容我们一共分,插入,选择,交换,归并这几个大类,那么今天小编给大家带来的就是插入排序
105 0
|
搜索推荐
排序(2)之选择排序
继插入排序后,今天小编就给大家另一个模块,选择排序的学习,那么话不多说,我们直接进入正题。
122 0
|
移动开发 算法 Shell
算法之排序5——希尔排序
依次比较待插入元素 i 和分组内另一个元素,就需要用到for循环语句;当h = 5 时,a[5]恰好是数组内第6个元素,也就是第一个待插入的元素,所以初始条件是 i = h,待插入的最后一个元素就是数组内最后一个元素,即终止条件为 i < a.length
136 0
|
索引
掌握常见的几种排序-选择排序
选择排序是一种简单的排序,时间复杂度是O(n^2),在未排序的数组中找到最小的那个数字,然后将其放到起始位置,从剩下未排序的数据中继续寻找最小的元素,将其放到已排序的末尾,以此类推,直到所有元素排序结束为止。
122 0
掌握常见的几种排序-选择排序
|
算法 搜索推荐 Java
排序:希尔排序(算法)
(注:如果想更好的理解希尔排序,请先看看我的上一篇博客插入排序,希望会对你有帮助。)
332 0
排序:希尔排序(算法)
|
算法 Shell
排序——希尔排序
排序——希尔排序
133 0
排序——希尔排序