竞争排序
竞争排序是一种排序算法。它优化了传统的选择排序，不是按顺序选择下一个排序的元素，而是选择优先队列。在传统选择排序中，从n个元素中选取下一个要排序的元素花费的时间复杂度为O(n)，而在竞争排序中，在花费O(n)的时间初始化优先队列之后，每次选取一个元素只要O(log n)。
原文地址：https://zh.wikipedia.org/wiki/%E7%AB%9E%E4%BA%89%E6%8E%92%E5%BA%8F
在知识共享 署名-相同方式共享 3.0协议之条款下提供
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 张拓的博客！
相关推荐
2022-11-29
Timsort
Timsort 是一种混合稳定的排序算法，源自合并排序和插入排序，旨在较好地处理真实世界中各种各样的数据。它使用了 Peter Mcllroy 的”乐观排序和信息理论上复杂性”中的技术，参见 第四届年度ACM-SIAM离散算法研讨会论文集，第467-474页，1993年。 它由 Tim Peters 在2002年实现，并应用于 Python编程语言。该算法通过查找已经排好序的数据子序列，在此基础上对剩余部分更有效地排序。 该算法通过不断地将特定子序列（称为一个 run ）与现有的 run 合并，直到满足某些条件为止来达成的更有效的排序。 从 2.3 版本起，Timsort 一直是 Python 的标准排序算法。 它还被 Java SE7 Android platform, GNU Octave, 谷歌浏览器, 和 Swift 用于对非原始类型的数组排序。 原文地址：https://zh.wikipedia.org/wiki/Timsort 在知识共享 署名-相同方式共享 3.0协议之条款下提供
2022-11-29
偏排序
在计算机科学里，偏排序是排序算法的一个放宽的变种。全排序返回的列表中，每个元素都按一定顺序出现，而偏排序返回的列表中，仅有 k 个最小(或 k 个最大)的元素是有序的。其他元素(第 k 个最小之外) 也可能被就地排序后存储，也可能被舍弃。这常见于流式偏排序中。偏排序最普遍的实例是计算某个列表的 “Top 100”。 就索引而言，偏排序后的列表中，对每一个从 1 到 k 的索引 i ，都有第 i 个元素与全排列后列表保持相同位置：偏排序后列表的第 i 个元素包含了输入列表中的第 i 个顺序统计量。 离线问题基于堆的解决方案当 k 固定时，堆允许一个简单的单次偏排序：向一个最大堆中插入输入中的前 k 个元素，然后遍历剩余的元素，依次加到堆中，并删除最大的那个。每个插入操作耗时 O(log k) ，总耗时达 O(n log k)。该算法适合求解第 k 小的值与配置在线算法. 另一个选择是为所有值构建一个最小堆(构建过程耗费 O(n)) 并将堆头移除，重复 K 次, 每次移除操作耗费 O(log n). 在该情况下，总的算法复杂度为 O(n+klog n)。 划分选择的解决方案进一步的放...
2022-11-29
侏儒排序
侏儒排序（英语：Gnome Sort）或愚人排序（英语：Stupid Sort）是一种排序算法，最初在2000年由伊朗计算机工程师Hamid Sarbazi-Azad（谢里夫理工大学计算机工程教授）提出，他称之为“愚人排序”。此后Dick Grune也描述了这一算法，称其为“侏儒排序”。此算法类似于插入排序，但是移动元素到它该去的位置是通过一系列类似冒泡排序的移动实现的。从概念上讲侏儒排序非常简单，甚至不需要嵌套循环。它的平均运行时间是O(n2)，如果列表已经排序好则只需O(n)的运行时间。 解释下面是侏儒排序的伪代码，其中使用的数组是下标从零开始的：12345678procedure gnomeSort(a[]): pos := 0 while pos < length(a): if (pos == 0 or a[pos] >= a[pos-1]): pos := pos + 1 else: swap a[pos] and a[pos-1] pos := pos...
2022-11-29
内省排序
内省排序（英语：Introsort）是由David Musser在1997年设计的排序算法。这个排序算法首先从快速排序开始，当递归深度超过一定深度（深度为排序元素数量的对数值）后转为堆排序。采用这个方法，内省排序既能在常规数据集上实现快速排序的高性能，又能在最坏情况下仍保持{\displaystyle O(n\log n)}的时间复杂度。由于这两种算法都属于比较排序算法，所以内省排序也是一个比较排序算法。 在快速排序算法中，一个关键操作就是选择基准点（Pivot）：元素将被此基准点分开成两部分。最简单的基准点击择算法是使用第一个或者最后一个元素，但这在排列已部分有序的序列上性能很糟。Niklaus Wirth为此设计了一个快速排序的变体，使用处于中间的元素来防止在某些特测序列上性能退化为{\displaystyle O(n^{2})}的状况。这个3基准中位数选择算法从序列的第一，中间和最后一个元素获取中位数来作为基准，虽然这个算法在现实世界的数据上性能表现良好，但经过精心设计的“破解序列”仍能大幅降低此变体算法的性能。这样就有攻击者精心设计序列发送到因特网服务器以进行拒绝服务（D...
2022-11-29
冒泡排序
冒泡排序（英语：Bubble Sort）又称为泡式排序，是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。 冒泡排序对{\displaystyle n}个项目需要O({\displaystyle n^{2}})的比较次数，且可以原地排序。尽管这个算法是最简单了解和实现的排序算法之一，但它对于包含大量的元素的数列排序是很没有效率的。 冒泡排序是与插入排序拥有相等的渐近时间复杂度，但是两种算法在需要的交换次数却很大地不同。在最坏的情况，冒泡排序需要{\displaystyle O(n^{2})}次交换，而插入排序只要最多{\displaystyle O(n)}交换。冒泡排序的实现（类似下面）通常会对已经排序好的数列拙劣地执行（{\displaystyle O(n^{2})}），而插入排序在这个例子只需要{\displaystyle O(n)}个运算。因此很多现代的算法教科书避免使用冒泡排序，...
2022-12-22
图书馆排序
图书馆排序，或空位插入排序是一种排序算法 ，它基于插入排序，但在每两个元素之间存在空位，以便于加速随后的插入。这个名字来自一个比喻： 假设一名图书管理员在一个长架上按字母顺序来整理书，从左边A开头的书，一直到右边Z开头的书，书本之间没有空格。如果图书管理员有一本开头为B的新书，当他找到了这本书在B区中的正确位置，他将不得不把从该位置后一直到Z的每一本书向右移动，就只是为了腾出空位放置这本新书。这就是插入排序的原理。但是，如果他在每一字母区后留有额外的空间，只要在B区之后还有空间，他插入书时就只需要移动少数几本书，而不会移动后面所有的书，这是图书馆排序的原理。 此算法由 Michael A. Bender、Martín Farach-Colton和Miguel Mosteiro 于2004年提出，并于2006年出版。 图书馆排序像插入排序一样，是稳定的排序算法，并且它是在线排序；然而，它被证明在大部分情况下具有O(n log n)的运行速度（相当于快速排序），而不是插入排序的O(n^2)。用于此改进的机制与跳过列表非常相似。本文没有给出完整的实现，也没有重要部分的确切算法，如插入和...
