图解，C语言希尔排序
嵌入式Linux
共 2956字，需浏览 6分钟
·
2021-03-02 23:07
希尔排序和插入排序很相似，有点像插入排序的升级版本。
希尔排序是希尔（Donald Shell）于1959年提出的一种排序算法。希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序，同时该算法是冲破O(n2）的第一批算法之一。
希尔排序也是一种插入排序算法，只不过在插入排序上突破了结界，达到了另一种顶峰的存在，这种顶峰使得时间复杂度变成「O(nLogn)~O(n^2)」。
假设我们需要给下面的数据进行排序
结合之前的文章，我们知道两个数据的插入排序就是比较两个数据的大小，然后进行排列。
希尔排序是通过分组+插入
首先我们排序的数量是 8 个，我们需要把数据分成 8/2 = 4组。
如下图
对上面4组的数据进行插入排序后得到
然后再继续分组 8➗2➗2 = 2 分成 2组
这两组数据再进行插入排序
如下图
这样之后，整个数据的排序差不多完成
我们在这个基础上再对整个队列执行一次插入排序，就会完成了整个队列的排序，因为之前已经对数据进行过排序，再进行插入排序的时候，效率会明显得到提升。
整个过程可以观看动态图片
代码实现看看
#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 main( int 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的时候，先进行第一次插入排序
步长等于2的时候，先进行第二次插入排序
步长等于1的时候，先进行第三次插入排序
具体过程可以查看插入排序的文章
最后一次进行插入排序之后，就会得到排序完成后的数列
评论