希尔(shell)排序

---

你的点赞评论就是对博主最大的鼓励
当然喜欢的小伙伴可以：点赞+关注+评论+收藏（一键四连）哦~

---

🍊自我介绍

  Hello,大家好，我是小珑也要变强（也是小珑），我是易编程·终身成长社群的一名“创始团队·嘉宾” 和“内容共创官” ,现在我来为大家介绍一下有关物联网-嵌入式方面的内容。

---

🍊希尔排序：直接插入排序改进算法

在众多排序算法中，希尔排序（Shell Sort）以其独特的优势脱颖而出。今天，我们就来深入探讨一下希尔排序算法。

希尔排序的基本概念

希尔排序是插入排序的一种改进版本。它的核心思想是将待排序的数组分割成若干个较小的子序列，对这些子序列分别进行插入排序，然后逐步减少子序列的间隔，最终对整个数组进行一次插入排序。这个过程使得数组在早期阶段就能够基本有序，从而大大减少了后期插入排序的工作量。

希尔排序的工作原理

1. 确定间隔序列

• 首先，我们需要确定一个间隔序列。常见的间隔序列有希尔序列，即间隔依次为数组长度的一半、三分之一、四分之一……直到间隔为 1。
• 例如，对于一个长度为 10 的数组，初始间隔可以是 5。

2. 子序列插入排序

• 按照确定的间隔，将数组分成若干个子序列。例如，间隔为 5 时，会有两个子序列：第一个子序列包含数组的第 1、6 个元素；第二个子序列包含数组的第 2、7 个元素，以此类推。
• 对每个子序列分别进行插入排序。

3. 逐步缩小间隔

• 当完成一轮对特定间隔子序列的插入排序后，缩小间隔，继续进行子序列的插入排序。直到间隔为 1 时，对整个数组进行一次插入排序。

希尔排序的优点和缺点

1. 优点

• 相比普通插入排序，希尔排序在早期阶段就能使数组基本有序，大大减少了后期的排序工作量，提高了效率。

• 对于大规模数据的排序，希尔排序通常比一些简单的排序算法表现更好。
  2. 缺点

• 希尔排序的性能取决于间隔序列的选择，不同的间隔序列可能会导致不同的性能表现。

• 时间复杂度的分析比较复杂，不像一些其他排序算法那样有明确的界限。

希尔排序的代码实现

//shell排序
void shell_sort(int *p,int n)
{int i = 0,j = 0,temp = 0;int k = 0;for(k = n / 2;k >= 1;k = k / 2){for(i = k;i < n;i++){temp = p[i];	for(j = i - k;j >= 0 && temp < p[j];j = j - k){p[j + k] = p[j];		}p[j + k] = temp;}}return ;
}

🍊代码演示

#include <stdio.h>//shell排序
void shell_sort(int *p,int n)
{int i = 0,j = 0,temp = 0;int k = 0;for(k = n / 2;k >= 1;k = k / 2){for(i = k;i < n;i++){temp = p[i];	for(j = i - k;j >= 0 && temp < p[j];j = j - k){p[j + k] = p[j];		}p[j + k] = temp;}}return ;
}void ouput(int *p,int n)
{int i = 0;for(i = 0;i < n;i++){printf("%d ",p[i]);	}printf("\n");
}int main()
{int a[] = {8,7,6,5,4,3,2,1};	int n = sizeof(a)/sizeof(a[0]);ouput(a,n);shell_sort(a,n);ouput(a,n);return 0;
}