排序算法---希尔排序---详解&&代码

简介: 排序算法---希尔排序---详解&&代码

希尔排序:

希尔排序:从整体宏观上有序逐步细节到局部的有序,希尔排序是一种改进版的插入排序,普通的插入排序算法中,是从第2个节点开始,依次插入到有序序列中,这种做法虽然“一次成形”,但研究发现时间效率上这么做并不划算。

希尔排序的时间复杂度为O(n*logn)



100个/2 = 50组 同组间隔50 每组元素是2个

50/2 = 25 同组间隔25 每组元素是4个

25/2 = 12 同组间隔12 每组元素是8 -----漏了后4个元素

12/2 = 6 同组间隔6 每组16个元素 — 还是漏掉了后4个

6/2 = 3 同组间隔3 每组32个元素 — 还是漏掉了后4个

3/2 = 1 同组间隔1 每组100个 — 最后一个看成特殊情况 直接全元素处理

1/2 = 0

代码:

void Shellsort(int data[], int len)
{
    int gru;    //组数
    int i,j;
    //希尔排序的轮次循环
    for(gru = len/2;gru!=0;gru/=2)  
    {
        //根据组数找插排的起始的元素
        for(i=gru;i<len;i++)
        {
            //单独一组的插排--可能是交替插排
            int temp = data[i];
            for(j =i-gru;j>=0;j-=gru)
            {
                if(data[j] > temp)
                    data[j+gru] = data[j];
                else
                    break;
            }
            data[j+gru] = temp;
        }
    } 
}
相关文章
|
22天前
|
算法 搜索推荐
数据结构算法--6 希尔排序和计数排序
**希尔排序**是插入排序的改进版,通过分组插入来提高效率。它逐步减少元素间的间隔(增量序列),每次对每个间隔内的元素进行插入排序,最终增量为1时进行最后一次直接插入排序,实现整体接近有序到完全有序的过程。例如,对数组`5, 7, 4, 6, 3, 1, 2, 9, 8`,先以间隔`d=4`排序,然后`d=2`,最后`d=1`,完成排序。计数排序则适用于0到100的数值,通过统计每个数出现次数,创建对应计数数组,再根据计数重建有序数组,时间复杂度为`O(n)`。
|
4天前
|
存储 算法 大数据
Python算法高手的必修课:深入理解分治法、贪心算法、动态规划,让你的代码更智能!
【7月更文挑战第9天】在Python算法学习中,分治法(如归并排序)将大问题分解为小部分递归解决;贪心算法(如货币找零)在每步选择局部最优解尝试达到全局最优;动态规划(如斐波那契数列)通过存储子问题解避免重复计算,解决重叠子问题。掌握这三种方法能提升代码效率,解决复杂问题。
|
11天前
|
算法 PHP
【php经典算法】冒泡排序,冒泡排序原理,冒泡排序执行逻辑,执行过程,执行结果 代码
【php经典算法】冒泡排序,冒泡排序原理,冒泡排序执行逻辑,执行过程,执行结果 代码
9 1
|
26天前
|
搜索推荐 算法
【排序】数据结构——排序算法概念及代码详解(插入、冒泡、快速、希尔)
【排序】数据结构——排序算法概念及代码详解(插入、冒泡、快速、希尔)
|
11天前
|
算法 搜索推荐 Shell
|
16天前
|
人工智能 搜索推荐 JavaScript
心得经验总结:排序算法:插入排序法(直接插入法和希尔排序法)
心得经验总结:排序算法:插入排序法(直接插入法和希尔排序法)
13 0
|
18天前
|
人工智能 算法 Java
java中经典算法代码整理
java中经典算法代码整理
20 0
|
18天前
|
机器学习/深度学习 搜索推荐 算法
【C/排序算法】:直接插入排序和希尔排序
【C/排序算法】:直接插入排序和希尔排序
12 0
|
19天前
|
算法 IDE 开发工具
c语言的经典算法代码
c语言进阶11-经典算法代码