C语言算法：希尔排序，图解

时间：2021-07-13 23:55:06

关键字：代码希尔排序

手机看文章

扫描二维码
随时随地手机看文章

[导读]C语言算法图解

来源：嵌入式linux | 排版：玩转嵌入式
希尔排序和插入排序很相似，有点像插入排序的升级版本。
希尔排序是希尔（Donald Shell）于1959年提出的一种排序算法。希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序，同时该算法是冲破O(n2）的第一批算法之一。
希尔排序也是一种插入排序算法，只不过在插入排序上突破了结界，达到了另一种顶峰的存在，这种顶峰使得时间复杂度变成「O(nLogn)~O(n^2)」。

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

结合之前的文章，我们知道两个数据的插入排序就是比较两个数据的大小，然后进行排列。
希尔排序是通过分组插入。
首先，我们排序的数量是8个，我们需要把数据分成8/2=4组，如下图所示：

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

然后，再继续分组8➗2➗2=2分成2组：

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

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

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

代码实现看看：
#include
#include
#include

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