文章目录
- 🍊自我介绍
- 🍊希尔排序：直接插入排序改进算法
- 希尔排序的基本概念
- 希尔排序的工作原理
- 希尔排序的优点和缺点
- 希尔排序的代码实现
- 🍊代码演示
你的点赞评论就是对博主最大的鼓励
当然喜欢的小伙伴可以：点赞+关注+评论+收藏（一键四连）哦~
🍊自我介绍
Hello,大家好，我是小珑也要变强（也是小珑），我是易编程·终身成长社群的一名“创始团队·嘉宾” 和“内容共创官” ,现在我来为大家介绍一下有关物联网-嵌入式方面的内容。
🍊希尔排序：直接插入排序改进算法
在众多排序算法中，希尔排序（Shell Sort）以其独特的优势脱颖而出。今天，我们就来深入探讨一下希尔排序算法。
希尔排序的基本概念
希尔排序是插入排序的一种改进版本。它的核心思想是将待排序的数组分割成若干个较小的子序列，对这些子序列分别进行插入排序，然后逐步减少子序列的间隔，最终对整个数组进行一次插入排序。这个过程使得数组在早期阶段就能够基本有序，从而大大减少了后期插入排序的工作量。
希尔排序的工作原理
- 确定间隔序列
- 首先，我们需要确定一个间隔序列。常见的间隔序列有希尔序列，即间隔依次为数组长度的一半、三分之一、四分之一……直到间隔为 1。
- 例如，对于一个长度为 10 的数组，初始间隔可以是 5。
- 子序列插入排序
- 按照确定的间隔，将数组分成若干个子序列。例如，间隔为 5 时，会有两个子序列：第一个子序列包含数组的第 1、6 个元素；第二个子序列包含数组的第 2、7 个元素，以此类推。
- 对每个子序列分别进行插入排序。
- 逐步缩小间隔
- 当完成一轮对特定间隔子序列的插入排序后，缩小间隔，继续进行子序列的插入排序。直到间隔为 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;
}
