vlambda博客
学习文章列表

C语言算法:希尔排序,图解

更多精彩推荐,请关注我们▼
玩转嵌入式
专注于单片机、ARM、嵌入式等硬件、软件设计经验的分享,并提供一定的技术支持。我已加入“维权骑士”(rightknights.com)的版权保护计划
602篇原创内容
Official Account

来源:嵌入式linux | 排版:玩转嵌入式

希尔排序和插入排序很相似,有点像插入排序的升级版本。

希尔排序是希尔(Donald Shell)于1959年提出的一种排序算法。希尔排序也是一种插入排序,它是简单插入排序经过改进之后的一个更高效的版本,也称为缩小增量排序,同时该算法是冲破O(n2)的第一批算法之一。

希尔排序也是一种插入排序算法,只不过在插入排序上突破了结界,达到了另一种顶峰的存在,这种顶峰使得时间复杂度变成「O(nLogn)~O(n^2)」。

C语言算法:希尔排序,图解

假设,我们需要给下面的数据进行排序:

C语言算法:希尔排序,图解

结合之前的文章,我们知道两个数据的插入排序就是比较两个数据的大小,然后进行排列。

希尔排序是通过分组+插入。

首先,我们排序的数量是8个,我们需要把数据分成8/2=4组,如下图所示:

C语言算法:希尔排序,图解

对上面4组的数据进行插入排序后得到:

C语言算法:希尔排序,图解

然后,再继续分组8➗2➗2=2分成2组:

C语言算法:希尔排序,图解

这两组数据再进行插入排序,如下图所示:

C语言算法:希尔排序,图解

这样之后,整个数据的排序就差不多完成了。

我们在这个基础上再对整个队列执行一次插入排序,就会完成了整个队列的排序,因为之前已经对数据进行过排序,再进行插入排序的时候,效率会明显得到提升。

C语言算法:希尔排序,图解

整个过程可以观看动态图片:

C语言算法:希尔排序,图解

代码实现看看:

  
    
    
  
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int shell_sort(int arr[],int n)
{
    register int i, j, tmp;
    int step;

    for(step = n/2; step > 0;step /= 2)/*增量步长*/
    {
        /*step = 4 2 1*/
        for(i = step; i < n; i++)
        {
            tmp = arr[i];
            j = i - step;
            for(;j >= 0 && tmp < arr[j];)
            {
                arr[j + step] = arr[j];
                j -= step;
            }
            arr[j + step] = tmp;

        }
    }
}

#define LENGTH 8

int mainint argc, int *argv[])
{
    int i;
    int arr[LENGTH] = {6,5,3,1,8,7,2,4};

    for(i=0;i<LENGTH;i++)
    printf("%d ",arr[i]);printf("\n");

    shell_sort(arr,LENGTH);

    for(i = 0;i < LENGTH;i++)
    printf("%d ", arr[i]);printf("\n");
}

代码输出:

  
    
    
  
6 5 3 1 8 7 2 4 
1 2 3 4 5 6 7 8 

接下来是代码图片解析,步长等于4的时候,先进行第一次插入排序:

C语言算法:希尔排序,图解
 
步长等于2的时候,先进行第二次插入排序:

C语言算法:希尔排序,图解

步长等于1的时候,先进行第三次插入排序,具体过程可以查看插入排序的文章:

C语言算法:希尔排序,图解

最后一次进行插入排序之后,就会得到排序完成后的数列:

C语言算法:希尔排序,图解

C语言算法:希尔排序,图解


C语言,动态展示经典排序算法
90 岁了,他用算法改变了世界!
CAN总线是数字信号,还是模拟信号?
惨了!买到了假芯片
盘点电子工程师常用的一些工具

点击“ 阅读原文 ”查看更多分享,欢迎点分享、收藏、点赞、在看