竞争排序
竞争排序是一种排序算法。它优化了传统的选择排序，不是按顺序选择下一个排序的元素，而是选择优先队列。在传统选择排序中，从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
冒泡排序
冒泡排序（英语：Bubble Sort）又称为泡式排序，是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。 冒泡排序对{\displaystyle n}个项目需要O({\displaystyle n^{2}})的比较次数，且可以原地排序。尽管这个算法是最简单了解和实现的排序算法之一，但它对于包含大量的元素的数列排序是很没有效率的。 冒泡排序是与插入排序拥有相等的渐近时间复杂度，但是两种算法在需要的交换次数却很大地不同。在最坏的情况，冒泡排序需要{\displaystyle O(n^{2})}次交换，而插入排序只要最多{\displaystyle O(n)}交换。冒泡排序的实现（类似下面）通常会对已经排序好的数列拙劣地执行（{\displaystyle O(n^{2})}），而插入排序在这个例子只需要{\displaystyle O(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-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)。用于此改进的机制与跳过列表非常相似。本文没有给出完整的实现，也没有重要部分的确切算法，如插入和...
2022-12-22
外排序
外排序（External sorting）是指能够处理极大量数据的排序算法。通常来说，外排序处理的数据不能一次装入内存，只能放在读写较慢的外存储器（通常是硬盘）上。外排序通常采用的是一种“排序-归并”的策略。在排序阶段，先读入能放在内存中的数据量，将其排序输出到一个临时文件，依此进行，将待排序数据组织为多个有序的临时文件。而后在归并阶段将这些临时文件组合为一个大的有序文件，也即排序结果。 外归并排序外排序的一个例子是外归并排序（External merge sort），它读入一些能放在内存内的数据量，在内存中排序后输出为一个顺串（即是内部数据有序的临时文件），处理完所有的数据后再进行归并。比如，要对900 MB的数据进行排序，但机器上只有100 MB的可用内存时，外归并排序按如下方法操作： 1.读入100 MB的数据至内存中，用某种常规方式（如快速排序、堆排序、归并排序等方法）在内存中完成排序。 2.将排序完成的数据写入磁盘。 3.读入每个临时文件（顺串）的前10 MB（ = 100 MB / (9块 + 1)）的数据放入内存中的输入缓冲区，最后的10 MB作为输出缓冲区。（实...
