臭皮匠排序
{{算法信息框 |class=排序算法 |image = |caption = 使用臭皮匠排序為一列數字進行排序的過程 |data=數組 |time = O(n^{\frac{\log 3}{\log 1.5}}) |space = O(n) |optimal=No }} 臭皮匠排序（）是一种采用分治法的低效排序算法，甚至慢于冒泡排序。在《算法导论》第二版第7章（快速排序）的思考题中被提到，是由Howard、Fine等教授提出的所谓“漂…
标签：#排序算法
共 36 篇文章
内省排序
内省排序（）是由大衛·穆塞爾在1997年设计的排序算法。这个排序算法首先从快速排序开始，当递归深度超过一定深度（深度为排序元素数量的对数值）后转为堆排序。采用这个方法，内省排序既能在常规数据集上实现快速排序的高性能，又能在最坏情况下仍保持O(n\log n)的时间复杂度。由于这两种算法都属于比较排序算法，所以内省排序也是一个比较排序算法。 在快速排序算法中，一个关键操作就是选择基准点（Pivot）：元素将被此基准点分开成两部分。最简单的…
珠排序
珠排序（）是一种自然排序算法，由約書亞·J·阿魯拉南達姆（Joshua J. Arulanandham）、和于2002年发展而来，并且在（EATCS）的新闻简报上发表了该算法。无论是电子还是实物上的实现，珠排序都能在 O(n) 时间内完成；然而，该算法在电子上的实现明显比实物要慢很多，并且只能用于对正整数序列进行排序。并且，即使在最好的情况，该算法也需要 O(n^2) 的空间。 算法概述 在珠排序中，一行（row）表示一个数字。如果一行…
比较排序
比较排序（）是排序算法的一种，通过一个抽象的内容比较操作（通常是“小于或等于”操作）来确定两个元素中哪个应该放在序列前面。该算法的唯一要求就是操作数满足全序关系： 如果 a\leq b并且 b\leq c那么 a\leq c（传递性）。 对于 a 或 b ，要不 a\leq b，要不 b\leq a（完全性）。 对于 a\leq b并且 b\leq a这种情况， a和 b都有可能被排在前面。这时输入的顺序就会决定最后的顺序。 比较排序类…
梳排序
梳排序（）是一種由弗拉基米爾·多博舍維奇（Wlodzimierz Dobosiewicz）於1980年所發明的不穩定排序算法，並由史蒂芬·萊西（Stephen Lacey）和理查德·博克斯（Richard Box）於1991年四月號的中推廣。梳排序是改良自泡沫排序和快速排序，其要旨在於消除「烏龜」，亦即在陣列尾部的小數值，這些數值是造成泡沫排序緩慢的主因。相對地，「兔子」，亦即在陣列前端的大數值，不影響泡沫排序的效能。 在泡沫排序中，只…
拓撲排序
在计算机科学领域，有向图的拓扑排序（）或拓撲定序（）是对其顶点的一种线性排序，使得对于从顶点 u 到顶点 v 的每个有向边 uv ， u 在排序中都在 v 之前。 例如，图形的顶点可以表示要执行的任务，并且边可以表示一个任务必须在另一个任务之前执行的约束；在这个应用中，拓扑排序只是一个有效的任务顺序。 当且仅当图中没有定向环时（即有向无环图），才有可能进行拓扑排序。 任何有向无环图至少有一个拓扑排序。已知有算法可以在-{}-线性时间内，…
桶排序
桶排序（）或所謂的箱排序，是一個排序演算法，工作的原理是將陣列分到有限數量的桶裡。每個桶再個別排序（有可能再使用別的排序演算法或是以遞迴方式繼續使用桶排序進行排序）。桶排序是鴿巢排序的一般化(generalization)。當要被排序的陣列內的數值是均勻分配的時候，桶排序使用線性時間（ \Theta(n) ）。 桶排序以下列程序進行： 設置一個定量的陣列當作空桶子。 尋訪序列，並且把項目一個一個放到對應的桶子去。 對每個不是空的桶子進行…
归并排序
归并排序（，或），是建立在归并操作上的一种有效的排序算法，效率為 O(n\log n) （大O符号）。1945年由约翰·冯·诺伊曼首次提出。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用，且各层分治递归可以同时进行。 概述 采用分治法: 分割：递归地把当前序列平均分割成两半。 整合：在保持元素顺序的同时将上一步得到的子序列整合到一起（归并）。 归并操作 归并操作（merge），也叫归并算法，指的是将两个已…
希尔排序
希爾排序（），也稱遞減增量排序算法，是插入排序的一種更高效的改進版本。希爾排序是非穩定排序算法。 希爾排序是基於插入排序的以下兩點性質而提出改進方法的： 插入排序在對幾乎已經排好序的數據操作時，效率高，即可以達到線性排序的效率 但插入排序一般來說是低效的，因為插入排序每次只能將數據移動一位 歷史 希爾排序按其設計者希爾（Donald Shell）的名字命名，該算法由1959年公佈。一些老版本教科書和參考手冊把該算法命名為Shell-Me…
堆排序
堆排序（）是指利用堆積;}-這種数据結構所設計的一種排序算法。-{zh-cn:堆;zh-tw:堆積;zh-hk:堆積;}-是一個近似完全二叉樹的結構，並同時滿足堆積的性質：即子節點的键值或索引總是小於（或者大於）它的父節點。 概述 若以升序排序說明，把陣列轉換成最大堆積（Max-Heap Heap），這是一種滿足最大堆積性質（Max-Heap Property）的二元樹：對於除了根之外的每個节点i, A[parent(i)] ≥ A[i…
基数排序
基数排序（）是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。 它是这样实现的：将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后，数列就变成一个有序序列。 基数排序的方式可以采用LSD（Least sig…
Bogo排序
{{算法信息框 | image = | class = 排序算法 | data = 数组 | time = O(\infin) | average-time = O(n\cdot n!)期望的位置交换次数增长地比期望比较次数快，是因为只需要比较几对元素就能发现元素是无序的，但是随机地打乱顺序所需要的交换次数却与数据长度成比例。在最差的情况下，交换和比较次数都是无限的，这就像随机投掷硬币可能连续任意次正面向上。 最好的情况是所给的数据是已…
偏排序
在计算机科学里，偏排序是排序算法的一个放宽的变种。全排序返回的列表中，每个元素都按一定顺序出现，而偏排序返回的列表中，仅有 k 个最小(或 k 个最大)的元素是有序的。其他元素(第 k 个最小之外) 也可能被就地排序后存储，也可能被舍弃。这常见于流式偏排序中。偏排序最普遍的实例是计算某个列表的 "Top 100"。 就索引而言，偏排序后的列表中，对每一个从 1 到 k 的索引 i ，都有第 i 个元素与全排列后列表保持相同位置：偏排序后…
外排序
外排序（External sorting）是指能够处理极大量数据的排序算法。通常来说，外排序处理的数据不能一次装入内存，只能放在读写较慢的外存储器（通常是硬盘）上。外排序通常采用的是一种“排序-归并”的策略。在排序阶段，先读入能放在内存中的数据量，将其排序输出到一个临时文件，依此进行，将待排序数据组织为多个有序的临时文件。而后在归并阶段将这些临时文件组合为一个大的有序文件，也即排序结果。 外归并排序 外排序的一个例子是外归并排序（Ext…
Timsort
Timsort 是一种混合稳定的排序算法，源自合并排序和插入排序，旨在较好地处理真实世界中各种各样的数据。它使用了 Peter Mcllroy 的"乐观排序和信息理论上复杂性"中的技术，参见 第四届年度ACM-SIAM离散算法研讨会论文集，第467-474页，1993年。 它由 Tim Peters 在2002年实现，并应用于 Python编程语言。该算法通过查找已经排好序的数据子序列，在此基础上对剩余部分更有效地排序。 该算法通过不断…
并行排序
并行排序算法是计算机并行计算能力大大发展之后，为了提高排序效率而提出的算法。 划分的设计方法 PSRS算法 Viliant归并算法 对数划分 串行算法直接并行化 模拟快速排序 *二叉树上模拟快速排序 串行算法简介：快速排序是一种较为高效的排序算法，它通过不断的划分待排序列为两段，使得前一段总小于或等于某个数，而后一段总大于某个数，这样每次划分就能确定一个数的最终位置。一般情况下，如果每次划分的两个子列大致等长，那么它的时间复杂度是O \…