建设局与住建局,入门seo技术教程,临沂网站公司,杭州做网站制作#x1f4d9;作者简介#xff1a; 清水加冰#xff0c;目前大二在读#xff0c;正在学习C/C、Python、操作系统、数据库等。 #x1f4d8;相关专栏#xff1a;C语言初阶、C语言进阶、C语言刷题训练营、数据结构刷题训练营、有感兴趣的可以看一看。 欢迎点赞 #x1f44d… 作者简介 清水加冰目前大二在读正在学习C/C、Python、操作系统、数据库等。 相关专栏C语言初阶、C语言进阶、C语言刷题训练营、数据结构刷题训练营、有感兴趣的可以看一看。 欢迎点赞 收藏 ⭐留言 如有错误还望各路大佬指正 ✨每一次努力都是一种收获每一次坚持都是一种成长✨ 前言 希尔排序作为一种高效的排序算法更是在排序算法这个舞台上展现出了自己独特的魅力听这个名字就感觉这个排序不简单本篇文章我将带领大家深入了解希尔排序。 1. 排序算法 在数据世界中排序算法是一种强大的工具能够将混乱无序的数据变得井然有序排序算法有很多种最常见也是最常用的排序算法有8种本期的主角是希尔排序。
1.1插入排序 希尔排序属于插入排序的一种在理解希尔排序之前我们需要先来了解一下插入排序的初阶——直接插入排序 1.1.1 直接插入排序 直接插入排序的原理非常好理解举个例子我们在完扑克牌时都会对牌的大小进行排序也就是组成顺子。 这就利用了直接直接插入排序7和10比较7小7再和5比较比5大所以7就插入到10的前边。 直接插入排序是一种简单直观的排序算法它的基本思想是将一个待排序的元素插入到已经排好序的元素序列中的适当位置从而得到一个新的、个数加一的有序序列。具体步骤如下
将待排序序列第一个元素视为已排序序列将其作为比较的基准。从第二个元素开始依次将每个元素插入到已排序序列中的适当位置。每次插入一个元素时都将该元素与已排序序列中的元素进行比较找到合适的位置插入。插入时将已排序序列中比待插入元素大的元素向后移动一位为待插入元素腾出位置。重复步骤3和步骤4直到将所有元素插入到已排序序列中。 过程如下图 理解了基本原理我们来进行代码实现在写排序算法时我们可以先写一趟的逻辑。我们需要记录开始比较的位置还要记录开始位置的后一个数据例如当end0时我们需要记录end的后一个位置数据从end开始一次向前移动并比较大小。如果tmp小于end位置的数据那么end位置的数据就向后移动一个位置。在这个过程中end要不断减减。具体代码如下 int end ;int tmp arr[end 1];while (end 0){if (tmp arr[end]){arr[end 1] arr[end];}else{break;}end--;}arr[end 1] tmp;//找到比tmp大的数据后跳出循环插入到end的后边
} 这也仅仅是一个数据插入的过程接下来我们要搞定这个数组所有的元素。我们可以利用一个for循环观察动图我们可以发现end是逐个向后的。但我们需要考虑越界的问题,i要小于n-1结束位置在最后的前一个位置。完整代码如下
void InsertSort(int* arr,int n)
{for (int i 0; i n-1; i){int end i;int tmp arr[end 1];while (end 0){if (tmp arr[end]){arr[end 1] arr[end];}else{break;}end--;}arr[end 1] tmp;}
} 1.1.2 希尔排序 由来 通过上述的插入排序过程我们可以发现插入排序的时间复杂度不低在局部有序的情况下插入排序很优。但存在最坏的情况就是逆序。逆序的情况下它的时间复杂度不亚于冒泡排序。 为了防止出现较坏的情况有位叫希尔的大佬对插入排序进行了优化就是在插入排序之前进行预排序。所以希尔排序的过程就可分为两部分 预排序插入排序 过程 希尔排序Shell Sort也称为缩小增量排序是插入排序的一种改进算法。它通过将待排序序列分割成若干子序列来进行排序最终将整个序列排序。 希尔排序的基本思想是先将待排序序列按照一定的增量进行分组对每个子序列进行插入排序然后逐步缩小增量再次进行分组和插入排序直到增量为1完成最后一次插入排序整个序列就变成有序的。 预排序 上边说到按照增量进行分组不好理解我们可以理解为步数gap当gap为1的时候就是插入排序gap为1就是相邻数据依次比较进行插入。当gap 1时都是预排序目的是让数组更接近于有序。 例如gap等于4那进行比较时就是对相邻间隔为4的数据进行调整位置插入。如下图 gap越小数据就越接近有序。 1.1.3 希尔排序的实现 理解了预排序的原理我们可以先来写一下预排序。
for (int i 0; i n - gap; igap)
{int end i;int tmp a[end gap];while (end 0){if (tmp a[end]){a[end gap] a[end];}else{break;}end - gap;}a[end gap] tmp;
} 这段代码看着是否很熟悉当gap为1时这段代码就是直接插入排序。这个是从第一个数据开始将数组中距离为gap数据进行调整。 那么接下来还要从第二个数据开始将距离为gap的数据进行调整。所以这里我们可以加一个循环确保每个数据都能被调整。
for (int i 0; i gap; i)
{for (int i 0; i n - gap; igap){int end i;int tmp a[end gap];while (end 0){if (tmp a[end]){a[end gap] a[end];}else{break;}end - gap;}a[end gap] tmp;}
}
这里我们可以优化一下我们这样写
for (int i 0; i n - gap; i)
{int end i;int tmp a[end gap];while (end 0){if (tmp a[end]){a[end gap] a[end];}else{break;}end - gap;}a[end gap] tmp;
} 大多数看到的书中都是这样写的或许在之前学习中很多同学不懂for循环这里为什么这样写。起初的逻辑是调整完一组后再调整下一组。那我们可不可以同时调整所有组
我们先调整第一个数据和它距离为gap的数据不急着将整组数据调整完接着开始从第二个数据开始与它距离为gap的数据进行调整…… 理解了这里我们继续上述的过程是在gap不变的情况下进行的预排序的过程是不断的改变gap的值来进行预排序。gap越小预排序后数据越接近有序。
void ShellSort(int* a, int n)
{int gap n;while (gap1){gap gap / 2;for (int i 0; i n - gap; i){int end i;int tmp a[end gap];while (end 0){if (tmp a[end]){a[end gap] a[end];}else{break;}end - gap;}a[end gap] tmp;}}
} 我们可以先令gap等于n数组的数据个数然后使用while循环判断gap是否大于1当gap 1时都是预排序进入while循环之后gap就整除2。到这里希尔排序就实现了。任何一个大于2的数除2最后都等于1除到最后gap等于2时进入while循环先执行gapgap/2最后一次执行时就刚好是插入排序。 当然gap也不一定就除2在一些书中也有这样的写法gapgap/31除3是因为有人觉得gap/2进行预排序的次数太多了但gap/3并不能保证除到最后所以就有了这种写法gapgap/31。
2. 复杂度 了解了直接插入排序和希尔排序那我们就来说一说它的复杂度问题它们的空间复杂度都为O(1)重点就在它们的时间复杂度。
2.1 直接插入排序 直接插入排序的时间复杂度好说假设有n个数据第一次从第一个数据开始最多比较1次第二次从第二个数据开始最多比较2次第三个最多比较3次……
那么它的执行次数T1234……n-1等差数列求和Tn-11*n/2首项加尾项乘以项数除以2所以它的时间复杂度最差达到O(N^2)。
2.2 希尔排序 希尔排序的时间复杂度计算非常复杂它的时间复杂度和gap有关。
当gap很大时例如gapn/3。整个数组逆序那么就有n/3组数据每组数据最多比较312次。 合计比较n/3*3n。 当gap等于n/9时整个数组逆序就会有n/9组数据每组有9个数据每组最多比较12345678次 合计比较n/9*364n。 当gap很小时如gap等于1时就只有1组数据进行调整排序此时的数据已经非常接近有序了再进行调整最差会比较n次估算一下合计n 由此可以看出希尔排序的性能图形为一个曲线函数。
希尔排序时间复杂度计算分析以上内容为了解 希尔排序的时间复杂度不好计算因为gap的取值方法很多导致很难去计算因此在很多书中给出的希尔排序的时间复杂度都不固定。在实际测试效果时众多答案中最符合的是O(N^1.3)。从这里就可以看出希尔排序它非常的不稳。 总结 本篇文章主要介绍了希尔排序希尔排序的时间复杂度与增量序列的选择有关它是一种不稳定的排序算法适用于中等规模的数据排序。希望本文对你有所帮助最后感谢阅读
