网上有关“O（n2）排序算法的总结”话题很是火热，小编也是针对O（n2）排序算法的总结寻找了一些与之相关的一些信息进行分析，如果能碰巧解决你现在面临的问题，希望能够帮助到您。
最近在慕课网上学习了O（n2）时间复杂度的相关算法，总算是对这些算法的优缺点有了详细的特点。其实对于任何的算法，没有优点和缺点，而是有相应的特点。所以我们应该结合不同的排序环境来选择不同的排序算法，从而达到在实现时间和执行效率上的平衡。这是因为，越是简单的排序算法，实现起来肯定是越容易，而且出现BUG的概率也不会太大。相反，复杂算法可能效率更高，但是出现问题的可能性也会更大。下面，我就结合O（n2）时间复杂度的四个经典排序算法，为您详细讲解这四个算法的特点。
定义：选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。
图示说明：
源码实现：
分析：通过选择排序的图示和源码我们可以看出来，选择排序要进行两次循环，而且最关键的是内层循环在每一次执行时都是全部执行完的。那我们有没有办法让内层循环不用每次都执行完呢？方法肯定是有的，这就是冒泡排序。
定义：冒泡排序（Bubble Sort），是一种计算机科学领域的较简单的排序算法。它重复地走访过要排序的元素列，一次比较两个相邻的元素，如果他们的顺序（如从大到小、首字母从A到Z）错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素已经排序完成。
图示说明：
源码实现：
分析：从图示和源码可以看出来，从执行次数上来说，冒泡排序是比选择排序的循环次数更少的。那是不是就可以说，如果待排序的数组中元素比较合适，冒泡排序在时间复杂度上是不是会比选择排序更好呢？真的是这样的吗？
其实不是的，经过多次测试验证，冒泡排序基本上是比选择排序的时间复杂度要差的，这是为什么呢？从源码中我们可以很明显的看出来，虽然冒泡排序是比选择排序执行次数少了，但是交换的次数明显增多了，而如果你对计算机程序指令的实现原理只要有一个基本的认识，就应该知道交换动作比赋值动作是需要更多指令操作的。所以说，最终冒泡排序大部分情况下，比选择排序的时间复杂度都要高。
既然交换动作这么消耗资源，那有没有一种方法，即能够减少内层循环的执行次数，又可以减少甚至是无需交换操作呢？这就要请出插入排序了。
定义：插入排序（Insertion?Sort）的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，即每步将一个待排序的记录，按其关键码值的大小插入前面已经排序的文件中适当位置上，直到全部插入完为止。
图示说明：
源码实现：
分析：从图示和源码可以看出来，插入排序（优化后的）是没有交换操作的，而且对于内层循环来说，如果待排序的元素是比较大的值，那内层循环执行的次数会非常的少。因此，如果原始数据基本上是有序的，那使用插入排序的效率会非常的高。在O（n2）级别的排序算法还可以再优化吗？如果可以从哪里优化呢？下面我们来介绍希尔排序，正是这个排序算法的提出，使得排序算法打破了O（n2）时间复杂度的禁锢。
定义：希尔排序(Shell's Sort)是插入排序的一种又称“缩小增量排序”（Diminishing Increment Sort），是直接插入排序算法的一种更高效的改进版本。该算法的基本思想是：把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，排序算法便终止。
对于希尔排序来说，最关键的就是增量该如何选取。这个增量该怎么确定，这还真是个数学难题，至今没有解答。但是通过大量的实验，还是有个经验值的。我们的例子给出的增量选取公式是：h = 3 *?h + 1，下面请看图示说明。
图示说明：
源码实现：
分析：从插入排序中我们知道，插入排在待排序数组基本有序时，插入排序的算法效率会非常高，所以我们可以这样认为，希尔排序的最终思想就是：先将整个待排记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，在对全体进行一次直接插入排序。
而希尔排序的效率之所以很高，就是因为这个基本思想确实很有用：即当h值大的时候，数据项每一趟排序需要移动元素的个数很少，但数据项移动的距离很长。这是非常有效率的。而当h减小时，每一趟排序需要移动的元素的个数增多，但是此时数据项已经接近于它们排序后最终的位置，这对于插入排序可以更有效率。正是这两种情况的结合才使希尔排序效率那么高。
对于增量的选取，可以称得上是一种魔法。在希尔的原稿中，他建议初始的间距为N/2，简单地把每一趟排序分成了两半。但是，这被证明并不是最好的数列。尽管对于大多数的数据来说这个方法还是比插入排序效果好，但是这种方法有时会使运行时间降到O(N2)，这并不比插入排序的效率更高。间隔序列中的数字互质通常被认为很重要：也就是说，除了1之外它们没有公约数。这个约束条件使每一趟排序更有可能保持前一趟排序已排好的效果。希尔最初以N/2为间隔的低效性就是归咎于它没有遵守这个准则。
总结：上面就是四种经典O（n2）级别排序算法的相关说明。其实在各种场合下选择排序和冒泡排序基本上是不会使用的，因为使用场景基本没有。而对于插入排序和希尔排序来说，在待排序数据基本有序的情况下，使用场景还是有的，比如一些日志文件中存储的日志，可能大部分的日志记录都是基于时间排序，只是在某些极端情况下导致一些日志晚存储了导致时间不一致。
我是徐建航， 这是我写的第31篇文章，欢迎你加入007社群，七天写一篇，一起写七年，七年之后一起去南极。
设序列长度为n,在最坏的情况下,时间复杂度为O(log2n)的算法是什么
冒泡排序的算法时间复杂度上O(n^2 )
冒泡排序是这样实现的：
首先将所有待排序的数字放入工作列表中。
从列表的第一个数字到倒数第二个数字，逐个检查：若某一位上的数字大于他的下一位，则将它与它的下一位交换。
重复2号步骤，直至再也不能交换。
冒泡排序的平均时间复杂度与插入排序相同，也是平方级的，但也是非常容易实现的算法。
选择排序
选择排序是这样实现的：
设数组内存放了n个待排数字，数组下标从1开始，到n结束。
i=1
从数组的第i个元素开始到第n个元素，寻找最小的元素。
将上一步找到的最小元素和第i位元素交换。
如果i=n－1算法结束，否则回到第3步
选择排序的平均时间复杂度也是O(n^2)的。
二分法
二分法的基本思想如下：
假设数据是按升序排序的，对于给定值x，从序列的中间位置开始比较，如果当前位置值等于x，则查找成功；若x小于当前位置值，则在数列的前半段中查找；若x大于当前位置值则在数列的后半段中继续查找，直到找到为止。
由于是数组是预先排序好的，所以可以采用折半查询的方式，每次抛掉待查询部分的一半
这样，长度为N的数组，只需要log2N次查询即可，2是对数的底。
例如，长度为7的数组，最多只需要3次就可以找到
O(log2n)只是表示是log2N同一数量级，因为有个取整的问题，而且也有可能在查询过程中就已经找到（也就是某个折半查询点正好是待查询数据），这样O(log2n)就是一个上限
关于“O（n2）排序算法的总结”这个话题的介绍，今天小编就给大家分享完了，如果对你有所帮助请保持对本站的关注！
本文来自作者[初双]投稿，不代表五洲号立场，如若转载，请注明出处：https://mip.tzwzszyy.cn/zlan/202507-13647.html
评论列表（3条）
我是五洲号的签约作者“初双”
本文概览：网上有关“O（n2）排序算法的总结”话题很是火热，小编也是针对O（n2）排序算法的总结寻找了一些与之相关的一些信息进行分析，如果能碰巧解决你现在面临的问题，希望能够帮助到您。最...
文章不错《O（n2）排序算法的总结》内容很有帮助