竞争排序
竞争排序是一种排序算法。它优化了传统的选择排序，不是按顺序选择下一个排序的元素，而是选择优先队列。在传统选择排序中，从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 许可协议。转载请注明来源 IT技术记录小站！
相关推荐
2022-12-22
插值排序
插值排序（interpolation sort）或称为直方图排序（histogram sort）。 是一种使用插值公式分散资料分而治之的排序算法。插值排序也是桶排序算法的一种变型。 插值排序递归算法插值排序也是一种桶排序，排序算法与桶排序相同，插值公式是把被排序的数字化为介于零到壹的数值，再乘以桶子的数量，得出被排序数字对应的桶子号码，以此号码分桶来实现桶排序。一个通用的插值公式是： 插值 = 取整数(((设算数 - 最小数) / (最大数 - 最小数)) * (桶子数量 - 1)) 插值排序递归算法流程 1.寻访序列，找出最大值与最小值，如果相等排序完成。 2.设置一个定量的阵列当作空桶子。 3.寻访序列，把项目一个一个放到插值对应的桶子去。 4.对每个不是空的桶子再次进行桶排序。 5.从不是空的桶子里把项目再放回原来的序列中。 插值排序递归算法实作JavaScript code: 123456789101112131415161718192021222324Array.prototype.bucketSort = function(){//--edit da...
2022-12-22
插入排序
插入排序（英语：Insertion Sort）是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到{\displaystyle O(1)}的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。 记载最早拥有排序概念的机器出现在1901至1904年间由赫尔曼·何乐礼发明出使用基数排序法的分类机，此机器系统包括打孔，制表等功能，1908年分类机第一次应用于人口普查，并且在两年内完成了所有的普查数据和归档。 赫尔曼·何乐礼在1896年创立的分类机公司的前身，为电脑制表记录公司（CTR）。他在电脑制表记录公司曾担任顾问工程师，直到1921年退休，而电脑制表记录公司在1924年正式改名为IBM。 概述Insertion Sort 和打扑克牌时，从牌桌上逐一拿起扑克牌，在手上排序的过程相同。 举例： 输入： {5 2 4 6 1 3}。 首先拿起第一张牌, 手上有 {5}。 拿起第二张牌 2, 把 2 insert ...
2022-12-22
并行排序
并行排序算法是计算机并行计算能力大大发展之后，为了提高排序效率而提出的算法。 划分的设计方法 PSRS算法 Viliant归并算法 对数划分 串行算法直接并行化 模拟快速排序 二叉树上模拟快速排序 串行算法简介：快速排序是一种较为高效的排序算法，它通过不断的划分待排序列为两段，使得前一段总小于或等于某个数，而后一段总大于某个数，这样每次划分就能确定一个数的最终位置。一般情况下，如果每次划分的两个子列大致等长，那么它的时间复杂度是{\displaystyle O\left(n\log n\right)}。 在PRAM-CRCW计算模型上利用二叉树网络模拟快速排序 由快速排序的过程，我们可以看到，快速排序实际上就是在构造一棵二叉树，让划分主元位于根节点，使得左子节点小于或等于根而右子节点大于根，最后对整棵二叉树进行一次中序遍历，便可以得到最后排好序的数列。 我们可以选n个处理器分别保存待排序数组A的n个元素，处理器{\displaystyle P_{i}}对应一个变量{\displaystyle X_{i}}用于存放主元元素的处理器号，以及两个变量L,R分别存放其左右儿子。开始时，...
2022-12-22
基数排序
基数排序（英语：Radix sort）是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。基数排序的发明可以追溯到1887年赫尔曼·何乐礼在列表机（Tabulation Machine）上的贡献[1]。 它是这样实现的：将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后，数列就变成一个有序序列。 基数排序的方式可以采用LSD（Least significant digital）或MSD（Most significant digital），LSD的排序方式由键值的最右边开始，而MSD则相反，由键值的最左边开始。 效率基数排序的时间复杂度是{\displaystyle O(k\cdot n)}，其中{\displaystyle n}是排序元素个数，{\displaystyle k}是数字位数。注意这不是说这个时间复杂度一定优于{\displaystyle ...
2022-12-22
词语定序
词语定序，或称定序（英语：Collation，目前没有公认的译名，但不少资讯领域者，如微软，根据其内涵而译作“定序”，或有译作“文字排序”），是指在计算机科学与图书馆学、词典编撰中书写信息的标准排序。如数值序或者字母序 。形式上说，定序方法对所有可能的标识符（即排序键）集合定义了一个全序，因此在信息项的集合上产生了一个全预序（因为具有相同的排序键的信息项没有预定次序）。 定序算法，如统一码定序算法，则定义如何比较两个字符串确定何者在先。 数值序或者编年序表示数值（或时间）的字符串按照其表示的数值，例如： “-4”, “2.5”, “10”, “89”, “30,000”. 注意可能会存在偏序情况，如”2”与”2.0”，”2e3”与”2000”。 字母序主条目：字母序字母序，也称词典序。常见问题有： 空白符（如空格符）如何处理； 附加符号。法语中把带附加符号的字符都当作基本字符来排序。德语的“电话簿序”中，Ä, Ö, Ü应当作为 “ae”, “oe”, “ue” 来排序。因此，姓Müller/Mueller具有相同的排序位置。西班牙语的Ñ作为一个单独字母排在N之后. 姓名排序时，...
2022-12-22
拓扑排序
在计算机科学领域，有向图的拓扑排序或拓扑测序是对其顶点的一种线性排序，使得对于从顶点{\displaystyle u} 到顶点{\displaystyle v}的每个有向边{\displaystyle uv}，{\displaystyle u} 在排序中都在{\displaystyle v}之前。 例如，图形的顶点可以表示要执行的任务，并且边可以表示一个任务必须在另一个任务之前执行的约束；在这个应用中，拓扑排序只是一个有效的任务顺序。 当且仅当图中没有定向环时（即有向无环图），才有可能进行拓扑排序。 任何有向无环图至少有一个拓扑排序。已知有算法可以在线性时间内，构建任何有向无环图的拓扑排序。 在图论中，由一个有向无环图的顶点组成的序列，当且仅当满足下列条件时，才能称为该图的一个拓扑排序（英语：Topological sorting）： 1.序列中包含每个顶点，且每个顶点只出现一次； 2.若A在序列中排在B的前面，则在图中不存在从B到A的路径。 算法卡恩算法卡恩于1962年提出了该算法。简单来说，假设L是存放结果的列表，先找到那些入度为零的节点，把这些节点放到L中，因为这些节点...
