注册网站的步骤,服装网站建设规划,易优cms收费吗,优化网站的网站个人主页#xff1a;点我进入主页 专栏分类#xff1a;C语言初阶 C语言程序设计————KTV C语言小游戏 C语言进阶 C语言刷题 数据结构初阶 Linux 欢迎大家点赞#xff0c;评论#xff0c;收藏。 一起努力,共赴大厂。 目录 一.前言
二.插入排序 … 个人主页点我进入主页 专栏分类C语言初阶 C语言程序设计————KTV C语言小游戏 C语言进阶 C语言刷题 数据结构初阶 Linux 欢迎大家点赞评论收藏。 一起努力,共赴大厂。 目录 一.前言
二.插入排序
2.1插入排序的思想
2.2代码实现
三.希尔排序
3.1希尔排序的思想
3.2代码实现
四.总结 一.前言 时隔一个多月我终于回来了。这段时间里由于一些不可避免的原因我没有能够抽出时间来撰写文章。但是今天我非常激动地给大家带来了一些全新的内容其中包含了插入排序和希尔排序的相关主题。在这一个月的沉淀中我对排序算法进行了深入的学习和实践通过对插入排序和希尔排序的研究我深刻领悟到它们在算法设计中的重要性。这两种排序算法不仅在理论上有着独特之处而且在实际应用中也展现出强大的性能。对于插入排序而言它的简单直观的思想使得它成为初学者入门的良好选择。通过逐步地将元素插入已排序的序列中我们可以在每一步保持部分有序性从而最终得到完全有序的结果。这种排序算法的易懂性使得它在教学和基础应用中广受欢迎。而希尔排序则是一种更为高级的排序算法它通过引入间隔序列的概念能够在一开始就以较大的步长对数据进行排序然后逐步减小步长最终实现全局有序。这种分阶段的排序思想使得希尔排序在大规模数据上表现出色相对于简单的插入排序它更具有高效性。
二.插入排序
2.1插入排序的思想
’ 我们先针对插入排序的某一次循环我们让前end个元素有序我们针对第end1的元素进行插入排序如果前面的元素大于这个元素我们就让它往后移动直到出现小于它的元素这样第一层循环就好了我们接下来写所有的排序我们直到前end个元素有序所以我们针对前end个元素进行让end先为0然后让end加加直到end小于n-1但是我们不能直接把end方在循环条件我们可以看下面的图片来感受一线插入排序。 在这张图片中我们可以深刻感受到插入排序的过程更详细的感受到插入排序的方法。
2.2代码实现
void InsertSort(int* a, int n)
{for(int i0;in-1;i){int end i;int tmp a[end 1];while (end 0){if (a[end] tmp){a[end 1] a[end];end--;}else{break;}}a[end 1] tmp;}
}
我们任意选择一趟排序例如针对这一趟排序我们的tmp存储了3end指向9 首先我们先让9和3进行比较9大于3我们让9向后进行移动然后end-- 我们继续进行比较最后我们可以得到 三.希尔排序
3.1希尔排序的思想 希尔排序的关键在于确定初始的 gap 值然后在每一轮迭代中逐步减小 gap。一般来说初始的 gap 可以选择数组长度的一半然后每轮迭代将 gap 除以 31直到 gap 缩小为 1。 希尔排序的性能相对于简单的插入排序有较大的提升尤其是对于中等大小的数组。这是因为希尔排序在每一轮迭代中都会对距离较远的元素进行比较和交换从而减少了插入排序中需要移动的元素的数量。 然而希尔排序并不是稳定的排序算法即相同元素的相对位置在排序前后可能会发生变。这是因为希尔排序的排序过程是基于比较和交换的而不是简单的元素移动。我们可以展示一下gap为5的动图。 3.2代码实现 void ShellSort(int *a, int n)
{int gapn;while(gap1){gap gap/3 1;for (int i 0; i n - gap; i){int end i;int tmp a[end gap];while (end 0){if (a[end] tmp){a[end gap] a[end];end - gap;}else{break;}}a[end gap] tmp;}}
}
我们针对gap4时进行讲解我们进行分组 进行循环end为0tmp为4进入第一次交换可以得到 我们的思想和插入排序一样希尔排序就是插入排序的进阶。对于希尔排序的时间复杂度为nlogn;
四.总结 希尔排序的主要思想是通过比较和交换不相邻的元素从而使得数据项能够更快地移动到正确的位置。这种分段的插入排序策略可以有效地减小序列的无序程度提高整体的排序效率。希尔排序的性能与所选取的间隔序列有关。一些常见的间隔序列包括希尔增量和序列9、5、3、2、1等。不同的间隔序列可能导致不同的性能表现因此在实际应用中选择适合特定情况的间隔序列是重要的。希尔排序的优点包括相对于简单的插入排序希尔排序对于中等大小的数据集表现更好。相对于一些其他复杂的排序算法希尔排序的实现相对简单。然而需要注意的是希尔排序并不稳定即相等元素的相对顺序在排序后可能发生改变。总体而言希尔排序是一种在实际应用中被广泛使用的排序算法尤其在需要对中等大小数据集进行排序时它的性能表现相对较好最后希望大家可以一件三连。
