偏排序

在計算機科學裡，偏排序是排序算法的一個放寬的變種。全排序返回的列表中，每個元素都按一定順序出現，而偏排序返回的列表中，僅有 k 個最小(或 k 個最大)的元素是有序的。其他元素(第 k 個最小之外) 也可能被就地排序後存儲，也可能被捨棄。這常見於流式偏排序中。偏排序最普遍的實例是計算某個列表的Top 100。就索引而言，偏排序後的列表中，對每一個從 1 到 k 的索引 i ，都有第 i 個元素與全排列後列表保持相同位置：偏排序後列表的第 i 個元素包含了輸入列表中的第 i 個順序統計量。

基本介紹

• 中文名：偏排序
• 外文名：Partial sorting
• 學科：數據結構
• 特點：僅部分元素是有序的
• 領域：排序算法
• 有關術語：順序統計量

離線問題

基於堆的解決方案

當k固定時，堆允許一個簡單的單次偏排序：向一個最大堆中插入輸入中的前k個元素，然後遍歷剩餘的元素，依次加到堆中，並刪除最大的那個。每個插入操作耗時O (log k )，總耗時達O ( n log k )。該算法適合求解第k小的值與配置線上算法。另一個選擇是為所有值構建一個最小堆(構建過程耗費O (n) )並將堆頭移除，重複K次，每次移除操作耗費O (log n ) .在該情況下，總的算法複雜度為O (n+klog n )。

劃分選擇的解決方案

進一步的放寬要求，只需要k個最小元素的列表，但不保證它們有序。這使得問題簡化為基於分區的選擇 ;原本的偏排序問題可以通過基於選擇算法來解決，這將得到一個包含前k個最小元素並保證它們有序的數組，總體耗費O ( n + k log k )。該算法方案的一個流行實現是結合快速選擇與快速排序，該結果常稱為"quickselsort"。

專門的排序算法

比上述更高效的，是基於歸併排序與快速排序的專門偏排序算法。在快速排序的變體裡，不需要對只包含最終排序後數組(從左邊界開始)的第k個位置之後元素的劃分(partition)，進行遞歸的排序。因此，如果支點(pivot)在k之後,我們的遞歸僅限於左邊的劃分(partition)：

function partial_quicksort(A, i, j, k)
      if i < j
         p ← pivot(A, i, j)
         p ← partition(A, i, j, p)
         partial_quicksort(A, i, p-1, k)
         if p < k-1
             partial_quicksort(A, p+1, j, k)

所得算法稱之為偏快速排序，且只需要耗時O ( n + k log k )，這在實踐中相當高效，尤其當一個選擇排序被用於k相對於n很小時的情況。然而，最壞的時間複雜度依然很糟糕,例如在選取了一個不好的支點(pivot)時。支點(pivot)的選擇沿著最壞線性時間線通常可以讓選擇算法的最壞情況稍好一些。

增量排序

增量排序是偏排序問題的一個線上算法版本。其中輸入被丟棄在前面，而k是未知的：給定一個k -sorted的數組，它應該可以擴展為偏排序部分，使之稱為( k +1) –sorted。

堆引出一個針對線上偏排序，複雜度為O ( n + k log n )的解決方案：先以線性時間“堆積”全部輸入數組，以產生一個最小堆。然後依次提取k次該堆的最小值。

一個更快的漸近增量排序可通過修改快速選擇獲得。由於Paredes和Navarro版本通過調用時維護了一個支點堆，故用增量排序求解數組A的最小元素可通過以下算法重複地完成：

Algorithm IQS( A  : array, i  : integer, S  : stack) returns the i 'th smallest element in A
If i = top( S ) :
Pop S
Return A [ i ]
Let pivot ← random [ i , top( S ))
Update pivot ← partition( A [ i  : top( S )), A [pivot])
Push pivot onto S
Return IQS( A , i , S )

堆疊S被初始化為長度為n的A。循環i = 0, 1, 2, ...中調用IQS( A , i , S )可完成對數組的k -sorting。這一系列調用的平均複雜度為O ( n + k log k )。最壞情況下是二次方，但這可以用中值算法的中位數替換隨機支點來解決。

順序統計量

在統計學中，樣本的第順序統計量（Order Statistics）即它從小到大排列時的第 個值，常用於非參數估計與推斷中。常見的順序統計量包括樣本的最大值、最小值、中位數等。

任給樣本，將其從小到大排成一列，記為：

則其第一順序統計量（即最小值）為，第順序統計量（即最大值）為。

隨機變數的累積分布函式由下式給出：

將累積分布函式求導可得其機率密度函式為：

排序

排序( sorting)是計算機科學中的一種基本操作，它的功能是將一個數據元素( 或記錄) 的任意序列重新排列成一個按關鍵字有序的序列。算法是解某一特定問題的一組有窮規則的集合。排序算法是電腦程式實現排序操作的算法。排序算法有多種多樣，常見的排序算法有冒泡排序、插入排序、希爾排序、選擇排序、快速排序、歸併排序、堆排序、基數排序、計數排序和靜態排序等，每種算法都有各自的優越性，同時也都存在著局限性。冒泡排序是最簡單的排序算法，在所有算法中平均效率是最低的，但便於理解，適用於記錄個數 n 較小的排序中； 選擇排序適用於記錄個數 n 較小而記錄本身信息量較大的排序中；插入排序適用於記錄個數 n 較小而原數組基本有序的排序中；希爾排序適用於記錄個數較大而記錄本身信息量較小的排序中；快速排序是從平均時間性能而言最佳的算法，適用於記錄個數n 較大而記錄無序的排序中；歸併排序適用於記錄個數 n 較大而記錄信息量也較大的排序中；堆排序適應於記錄個數較大的數組，但是對記錄較少的數組效率低；基數排序適合於n 值很大而關鍵字較小的序列；計數排序和靜態排序都是基於計數思想的排序算法，只是它們的計數方式不同。計數排序是根據記錄本身的大小直接得到已排序數組的索引值，但是受到數據範圍的影響較大，它適合記錄個數 n 較大而數據範圍較小的自然數排序中；靜態排序是通過對原數組中任意兩個記錄的比較得到比其小的記錄的個數，從而求出其在已排序數組中的索引值，適應於記錄個數n 較小而記錄信息量非常大的排序中。

排序算法的分類方法有很多種。如果按算法穩定性可以分為穩定排序和不穩定排序。由於待排序的記錄數量不同，使得排序過程中涉及的存儲器不同，可將排序算法分為內部排序和外部排序兩大類。比較類排序需要比較兩個記錄的大小，根據比較結果將記錄從一個位置移動到另一個位置，逐漸逼近並最終求出目標數組，如插入排序、選擇排序、快速排序等；計數類排序通過比較兩個記錄的大小或者統計記錄的個數得出所有記錄在目標數組中的索引值，從而直接求出目標數組，根據計數方式不同可以把計數類排序分為比較計數類排序和統計計數類排序，如靜態排序屬於比較計數類排序，計數排序和計算排序屬於統計計數類排序；基數類排序是藉助“分配”和“收集”兩種操作對單邏輯關鍵字進行操作，經多次操作後最終求得目標數組，如基數排序。