數值不等於記錄
假設有限陣列有 個記錄,每個記錄都有來自全序集合的鍵值及不同身分。我們要選出鍵值最小的恰好 個記錄,其中 。鍵值可以重複。任務未必要求輸出已排序。所選鍵值的多重集唯一,但若平手沒有規則,所選身分未必唯一。我們約定邊界平手時優先選原始位置較早的記錄,並按原輸入次序輸出所選記錄。
當 ,返回空列表。當 ,按輸入次序返回所有記錄。對 ,令 是由一開始計算、按重數排列的第 小鍵值。把記錄分為鍵值小於、等於及大於 的三組,分別稱為 。由排名定義,
定義 4.2.1
(帶最早位置平手規則的最小 k 選取)
設鍵值按重數排序為 。若恰好 個記錄所成集合 的鍵值多重集等於 ,就稱 為最小 選取;等價地, 中每個鍵值都不大於 以外的每個鍵值。在所有最小 選取中,最早位置選取是指其中來自 的記錄在輸入中位置最早的那一個,並按輸入次序返回。
因此每個有效答案必須包含所有 、排除所有 ,並從 恰好選 個記錄。把所有鍵值不大於 的記錄都取出,可能取出太多。邊界規則按原位置選取 中最早的 個記錄。
反例模式
保留所有不大於閾值的鍵值
斷言:要取最小的 個記錄,只需求出 ,再保留所有鍵值不大於 的記錄。取鍵值 及 。排序後為 ,所以 ,而每個鍵值都不大於 :此規則保留全部五個記錄,而不是三個。這裏 的鍵值是 ,所以 ,三個鍵值為 的記錄中只可保留 個。修正後的規則保留位置 的記錄,按輸入次序鍵值為 。邊界上的平手,正是閾值過濾與計數結果不一致之處。
觀察邊界
例題 4.2.2
(有重複鍵值的列表中的第 4 小值)
對數列 的第 小值,選首項 為樞紐。較小、相等、較大部分分別是 、、。由於 ,答案是 ,毋須再分割。核對:排序後為 ,第四項是 。
在預設追蹤中,、、。元件展示可重現的固定首項樞紐選擇追蹤,並非隨機算法,也不選取記錄身分。若七個記錄按輸入次序命名為 ,按我們的平手規則所選身分為 :三個小於 的鍵值,以及最早等於 的記錄。返回 保持輸入次序,但沒有按鍵值排序。元件上方的段落在靜態閱讀時提供鍵值分割。
例題 4.2.3
(三個邊界記錄中選兩個,並保持輸入次序)
取鍵值 ,位置為 ,。排序後為 ,所以 、(鍵值 )、(位置 )。鍵值 的配額是 。第二次掃描:位置 (鍵值 ,已用配額 )輸出;位置 (鍵值 )跳過;位置 (鍵值 ,已用配額 )輸出;位置 因配額用完、位置 因鍵值大於 而跳過;位置 (鍵值 )輸出。結果是位置 ,鍵值為 。第三個鍵值為 的記錄被捨棄,儘管它的鍵值等於 。
例題 4.2.4
(退化情況:k = 0、k = n 及全部鍵值相等)
時,任何輸入的答案都是空列表,不需要閾值。 時,按輸入次序返回所有記錄。若鍵值為 而 ,則 、、、,配額為 :第二次掃描輸出位置 和 ,之後不再輸出。不等式 成立,正如排名定義所保證。當 時,同一掃描返回全部四個記錄,與 的規則一致。
為何構造正確
先用任何正確的排名選擇程序求 。掃描原陣列一次以計算 ,再掃描一次:輸出每個鍵值小於 的記錄,並只輸出最早的 個鍵值等於 的記錄;忽略大於 的鍵值。它由左至右讀取原位置,故輸出保持輸入次序,而相等鍵值的身分選擇是確定的。
定理 4.2.5
(兩次掃描給出最早位置選取)
設 ,,。兩次掃描的程序恰好輸出 個記錄,按輸入次序排列,且輸出集合就是最早位置的最小 選取。此外,每個最小 選取都包含 的全部記錄、不含 的任何記錄,並恰好含 中的 個記錄。
證明
(計算鍵值個數並迫出邊界分組)
排名不等式 給出 ,所以邊界記錄的配額可以填滿,第二次掃描輸出 個記錄。排序後的鍵值中恰有 個小於 ,即 ;而 全部等於 ,因為它們不大於 又不小於 。輸出的鍵值是 的 個鍵值加上 個 ,其多重集是 ,所以輸出集合是最小 選取。
再設 為任意最小 選取,即 中每個鍵值都不大於 以外的每個鍵值。若有 在 之外,則 中每個鍵值都不大於 的鍵值,而它小於 ;於是 ,得 ,與 矛盾。若有 在 之內,則 以外每個鍵值都不小於 的鍵值,而它大於 。但 有 個記錄, 只剩 個位置可容納它們,所以 中必有一個鍵值不大於 的記錄在 之外,矛盾。因此 是 加上 中的 個記錄;最早位置規則選 中最早的 個,正是掃描所輸出的。
證明透視
排名不等式與平手規則用在哪裏
計數步驟只用到小於 的鍵值個數 及 這個事實,從不查看哪個記錄帶哪個鍵值,所以求 可用任何正確的排名程序。 的左半令配額 至少為一,即確實需要一個邊界記錄;右半令配額可以達成。若誤把 取成 ,不等式可能不成立,掃描便可能輸出錯誤個數的記錄。最早位置規則與鍵值多重集無關,它只在鍵值相等的記錄之間作選擇,使輸出被唯一確定。
元件展示一種求 的方法。三路分割時,設目前由一開始計算的局部排名為 :若 ,保留較小部分;若 ,在相等部分停止;否則保留較大部分,並把 改為 。排名調整針對目前子問題。元件的特定追蹤在相等部分停止;單靠其選擇結果不會保留或選出記錄身分。
成本、修改輸入及串流替代法
若排名程序使用 次鍵值比較,兩次額外掃描使用 次比較。總成本繼承所用程序的最壞情況或期望保證。若該程序會修改輸入,應在鍵值的私人副本上執行,使第二次掃描仍按原始次序看見記錄。鍵值副本需要 個額外鍵值槽,另有 個輸出記錄;選擇程序可能需要更多工作空間。另一種設計是在修改前為記錄保存原始索引,按 選最小的 個配對,然後以 次比較排序所選索引,恢復輸入次序。按配對選取才會落實位置最早的平手規則。
概念視角結構
把鍵值與位置配對,令所有鍵值相異
把每條記錄換成配對 ,按字典序比較。這些配對全都相異,所以排名為 的配對 是真正的門檻,而位置最早的選擇恰是配對不超過 的那些記錄。對鍵值 及 ,排序後的配對以 開頭,故 ,所選位置為 。
固定首項樞紐的快速選擇可能需要 次比較。適當的均勻隨機樞紐及三路分割,在所述模型下有期望線性的選擇界;它不是每次執行的最壞情況界,元件也沒有模擬隨機性。若輸出還須按鍵值排序,使用比較排序需額外 次比較。
對 的串流,另一種契約是保留至多 個記錄的最大堆,按 字典序排列。鍵值全序及互異索引令這些配對形成全序。每次輸入後,它包含最小的 個配對:若堆未滿,插入新配對;若堆已滿且新配對不小於最大值,丟棄新配對;若堆已滿且新配對較小,替換最大值並恢復堆次序。歸納法可證不變量。此法使用 次比較,儲存 個記錄。堆次序不是輸出次序;若要按原始索引返回,還需另行排序。 時不儲存任何記錄。
常見錯誤
(在重排後的陣列上做第二次掃描)
設記錄 的鍵值為 ,。則 、,最早位置選取是 ,按 返回。若排名程序已把陣列重排為 ,而第二次掃描讀取的就是這個陣列,它會輸出 ,然後輸出遇到的第一個 ,即 。身分錯了,次序也不是輸入次序。應掃描原始記錄,或保留了原位置的副本。
常見錯誤
(鍵值相等時仍替換堆的最大值)
在串流版本中取 ,三個鍵值同為 的記錄依次以索引 到達。堆中有 與 。新到的 按字典序大於最大值 ,所以被丟棄。若鍵值不大於最大值(含相等)就替換,便會保留較遲的記錄而丟掉較早的,違反最早位置規則。
習題
快速檢查
(鍵值為 ,各記錄按輸入次序有不同身分,且 。求 、、,及按上述平手規則選出的原位置。)
先把鍵值按重數排序,再讀出第四項。
解答 · 答案
排序後鍵值為 ,所以 、、。選位置 :所有小於 的鍵值,加上最早的 ,按原次序返回。
快速檢查
(若平手跨越邊界,為何返回所有鍵值不大於 的記錄是錯的?)
數一數返回的記錄個數,再與 比較。
解答 · 答案
對上一題的鍵值,這會返回全部六個記錄而非四個;三個邊界相等記錄中只需一個。
快速檢查
(若排名選擇重排了輸入的唯一副本,但輸出必須按原次序排列,會有甚麼額外問題?)
想一想第二次掃描讀取的是甚麼。
解答 · 答案
選擇過程可能破壞原次序。應保存未改動的輸入副本,或保留原始索引並明確恢復所需次序;只知道所選鍵值不足以恢復記錄身分。