中位切割演算法
中位切割演算法（）是Paul Heckbert於1979年提出來的演算法。概念上很簡單，卻也是最知名、應用最為廣泛的減色演算法（）。常見的影像處理軟體如Photoshop、GIMP...等，都使用了這個演算法或其變種。 演算法 假如你有任意一張圖片，想要降低影像中的顏色數目到256色。 將圖片內的所有像素加入到同一個區域 對於所有的區域做以下的事： 計算此區域內所有像素的RGB三元素最大值與最小值的差。 選出相差最大的那個顏色（R或G或…
标签：#排序算法
共 36 篇文章
逆序对
在计算机科学和离散数学中，一个序列的逆序（inversion）对，是失去自然次序的元素对。 定義 逆序 設\ \pi \ 為一個排列，如果\ i 而且 \ \pi(i) > \pi(j) \ ， 這個位置（有称为“序位”）对 \ (i, j) \ ，或者這个元素对 \ \bigl(\pi(i), \pi(j)\bigr) \ ，被稱為是 \ \pi \ 的一個逆序。 逆序集是所有逆序的集合。一個排列 \ \pi \ 的使用基于位置表示法…
煎餅排序
煎饼排序（）指的是将大小不同的一摞煎饼按大小排序的数学问题，其中每次只能从任意位置铲起上方全部煎饼并翻面。“煎饼数”（）是指给定煎饼的张数时，最坏情况下需要的最少翻面次数。这个问题最早由美国几何学家雅各布·E·古德曼提出。它属于排序问题的变种。煎饼排序的目标和传统排序算法最小化比较次数不同，因为它每次操作只允许反转序列的，所以需要最小化反转前缀次数。焦煎饼排序是煎饼排序的变种问题，每张煎饼都有一面是烤焦的，最终除了按照大小排序以外还要让…
快速排序
快速排序（），又稱分区交換排序（），是一種排序演算法，最早由東尼·霍爾提出。在平均狀況下，排序 n 個項目要 \ O (n\log n) （大O符号）次比較。在最壞狀況下則需要 O (n^2) 次比較，但這種狀況並不常見。事實上，快速排序 \Theta(n\log n) 通常明顯比其他演算法更快，因為它的內部循环可以在大部分的架構上很有效率地達成。 演算法 快速排序使用分治法策略來把一個序列分為较小和较大的2个子序列，然后递归地排序两个…
冒泡排序
冒泡排序（）又稱為泡式排序，是一種簡單的排序算法。它重複地走訪過要排序的數列，一次比較兩個元素，如果它們的順序錯誤就把它們交換過來。走訪數列的工作是重複地進行直到沒有再需要交換，也就是說該數列已經排序完成。這個算法的名字由來是因為越小的元素會經由交換慢慢「浮」到數列的頂端。 冒泡排序對n個項目需要O(n^2)的比較次數，且可以原地排序。儘管這個演算法是最簡單瞭解和實作的排序算法之一，但它對於包含大量的元素的數列排序是很沒有效率的。 冒泡…
詞語定序
詞語定序，或稱定序（，目前没有公认的译名，但不少資訊領域者，如微軟，根據其內涵而譯作「定序」，或有译作“文字排序”），是指在计算机科学与图书馆学、词典编撰中书写信息的标准排序。如或者字母序 。形式上说，定序方法对所有可能的标识符（即）集合定义了一个全序，因此在信息项的集合上产生了一个（因为具有相同的的信息项没有预定次序）。 定序算法，如統一碼定序演算法，則定义如何比较两个字符串确定何者在先。 数值序或者编年序 表示数值（或时间）的字符串…
插入排序
插入排序（）是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到 O(1) 的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。 記載 最早擁有排序概念的機器出現在1901至1904年間，由赫爾曼·何樂禮發明使用基數排序法的分類機，此機器系統包括打孔，制表等功…
排序算法
在計算機科學與數學中，一個排序算法（）是一種能將一串資料依照特定排序方式排列的算法，排序後的資料即可放在有序陣列。最常用到的排序方式是數值順序以及字典順序。有效的排序算法在一些算法（例如搜尋算法與）中是重要的，如此這些算法才能得到正確解答。排序算法也用在處理文字資料以及產生人類可讀的輸出結果。基本上，排序算法的輸出必須遵守下列兩個原則： 輸出結果為遞增序列（遞增是針對所需的排序順序而言） 輸出結果是原輸入的一種排列、或是重組 雖然排序算…
鸽巢排序
鸽巢排序（），也被称作基数分类，是一种时间复杂度为 O(n) （大O符號）且在不可避免遍历每一个元素并且排序的情况下效率最好的一种排序算法。但它只有在差值（或者可被映射在差值）很小的范围内的数值排序的情况下实用。 当涉及到多个不相等的元素，且将这些元素放在同一个「鸽巢」的时候，算法的效率会有所降低。为了简便和保持鸽巢排序在适应不同的情况，比如两个在同一个存储桶中结束的元素必然相等。 我们一般很少使用鸽巢排序，因为它很少可以在灵活性、简便…
鸡尾酒排序
鸡尾酒排序（），亦為定向冒泡排序，雞尾酒攪拌排序，攪拌排序（也可以視作選擇排序的一種變形），漣漪排序，來回排序或快乐小時排序，是冒泡排序的一種变形。此演算法与冒泡排序的不同處在於排序時是以双向在序列中進行排序。 伪代码 将一个序列由小到大进行排序： function cocktail_sort(list, list_length){ // the first element of list has index 0 bottom = 0;…
锦标赛排序
锦标赛排序（）是一种排序算法。它优化了传统的选择排序，不是按顺序选择下一个排序的元素，而是选择优先队列。在传统选择排序中，从n个元素中选取下一个要排序的元素花费的时间复杂度为O(n)，而在锦标赛排序中，在花费O(n)的时间初始化优先队列之后，每次选取一个元素只要O(log n)。
选择排序
选择排序（）是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。 选择排序的主要优点与数据移动有关。如果某个元素位于正确的最终位置上，则它不会被移动。选择排序每次交换一对元素，它们当中至少有一个将被移到其最终位置上，因此对 n 个元素的表进行排序总共进行至多 (n-1) 次…
耐心排序
耐心排序（）是將陣列的元素分類成很多堆再串接回陣列的一種排序演算法。注意「」一詞在此並非「耐心」之意，而是一種單人紙牌遊戲的名字（英文中又稱爲card solitaire）。 操作解說 建立一個堆陣列 比較目前指向的元素和每個堆的第一個元素，計算出比目前元素小的堆數量 若目前元素比所有堆的第一個元素大，建立新的堆並加入到堆陣列中，否則將目前元素加入到第「比目前元素小的堆數量」個堆 分類完後將每個堆反序然後對每個堆再做耐心排序 最後將每個…
比較計數排序
比較计数排序（）是一种稳定的线性时间排序算法，此種演算法時間複雜度雖然是平方時間，但它是擁有較強抗干擾能力和穩固性的排序演算法。 比較计数排序的特征 此種演算法把每個項目與其它項目作比較，計數出每個項目大於(或小於)它的項目個數，此數字及可當作各個項目排序的基準值。此種演算法與泡沫排序一樣時間複雜度都是平方時間，不受傳統電腦科學青睞，但容錯率超群。 Python 2.7 實现 def compare_counter_sort(l): C…
慢速排序
慢速排序（）是一種排序演算法。其基於合併排序的分而治之及遞迴的思想，並故意設計使排序過程非常緩慢。慢速排序由安德烈·布羅德（Andrei Broder）及豪爾赫·斯托爾菲（Jorge Stolfi）在1986年發表的論文《Pessimal Algorithms and Simplexity Analysis》（論文名稱是漸進最優算法及計算複雜性理論的戲仿）中提出。 演算法 慢速排序是一種原地算法的递归算法。 在简单的伪代码中，此演算法可…
图书馆排序
图书馆排序（），或空位插入排序是一种排序算法 ，它基于插入排序，但在每两个元素之间存在空位，以便于加速随后的插入。这个名字来自一个比喻：假设一名图书管理员在一个长架上按字母顺序來整理书，从左边A開頭的書，一直到右边Z開頭的書，书本之间没有空格。如果图书管理员有一本開頭為B的新书，当他找到了這本書在B區中的正确位置，他将不得不把從該位置後一直到Z的每一本书向右移动，就只是为了腾出空位放置这本新书。这就是插入排序的原理。但是，如果他在每一字…
侏儒排序
侏儒排序（）或愚人排序（）是一种排序算法，最初在2000年由伊朗计算机工程师哈米德·薩爾巴齊-阿扎德（Hamid Sarbazi-Azad，谢里夫理工大学计算机工程教授）提出，他称之为“愚人排序”。此后也描述了这一算法，称其为“侏儒排序”。此算法类似于插入排序，但是移动元素到它该去的位置是通过一系列类似冒泡排序的移动实现的。从概念上讲侏儒排序非常简单，甚至不需要嵌套循环。它的平均运行时间是 O(n^2) ，如果列表已经排序好则只需 O(…
插值排序
插值排序（）或稱為直方圖排序（）是一種使用插值公式分散資料分而治之的排序演算法。插值排序也是桶排序演算法的一種變型。 插值排序遞歸算法 插值排序也是一種桶排序，排序演算法與桶排序相同，插值公式是把被排序的數字化為介於零到壹的數值，再乘以桶子的數量，得出被排序數字對應的桶子號碼，以此號碼分桶來實現桶排序。一個通用的插值公式是： 插值 = 取整數(((設算數 - 最小數) / (最大數 - 最小數)) (桶子數量 - 1)) 插值排序遞…
奇偶排序
奇偶排序（），或奇偶换位排序、砖排序，是一种相对简单的排序算法，最初发明用于有本地互连的并行计算。这是与冒泡排序特点类似的一种比较排序。 该算法中，通过比较数组中相邻的（奇-偶）位置数字对，如果该奇偶对是错误的顺序（第一个大于第二个），则交换。下一步重复该操作，但针对所有的（偶-奇）位置数字对。如此交替进行下去。 处理器数组的排序 在并行计算排序中，每个处理器对应处理一个值，并仅有与左右邻居的本地互连。所有处理器可同时与邻居进行比较、交…
计数排序
计数排序（）是一种稳定的线性时间排序算法。该算法于1954年由哈羅德·H·西華德提出。计数排序使用一个额外的数组 C ，其中第i个元素是待排序数组 A 中值等于 i 的元素的个数。然后根据数组 C 来将 A 中的元素排到正确的位置。 计数排序的特征 当输入的元素是 n 个 0 到 k 之间的整数时，它的运行时间是 \Theta(n+k) 。计数排序不是比较排序，因此不被 \Omega(n\log n)的下界限制。 由于用来计数的数组 C…