本節(jié)書(shū)摘來(lái)自異步社區(qū)《編程珠璣（第2版?修訂版）》一書(shū)中的第2章2.5節(jié)原理，作者【美】Jon Bentley，更多章節(jié)內(nèi)容可以訪(fǎng)問(wèn)云棲社區(qū)“異步社區(qū)”公眾號(hào)查看。

2.5　原理
排序。排序最顯而易見(jiàn)的用處是產(chǎn)生有序的輸出，該輸出既可以是系統(tǒng)規(guī)范要求的一部分，也可以是另一個(gè)程序（也許是一個(gè)二分搜索程序）的前期準(zhǔn)備工作。但是在變位詞問(wèn)題中，排序并不是關(guān)注的焦點(diǎn)。排序是為了將相等的元素（本例中為標(biāo)識(shí)）集中到一起。這些標(biāo)識(shí)產(chǎn)生了另外一個(gè)排序應(yīng)用：將單詞內(nèi)字母排序使得同一個(gè)變位詞類(lèi)中的單詞具有標(biāo)準(zhǔn)型。通過(guò)給每條記錄添加一個(gè)額外的鍵，并按照這些鍵進(jìn)行排序，排序函數(shù)可以用于重新排列磁盤(pán)文件中的數(shù)據(jù)。在第三部分，我們還會(huì)多次回顧排序這個(gè)主題。

二分搜索。該算法在有序表中查找元素時(shí)極為高效，并且可用于內(nèi)存排序或磁盤(pán)排序。唯一的缺陷就是整個(gè)表必須已知并且事先排好序。基于該簡(jiǎn)單算法的思想在許多應(yīng)用程序中都有應(yīng)用。

標(biāo)識(shí)。當(dāng)使用等價(jià)關(guān)系來(lái)定義類(lèi)時(shí)，定義一種標(biāo)識(shí)使得類(lèi)中的每一項(xiàng)都具有相同的標(biāo)識(shí)，而該類(lèi)以外的其他項(xiàng)則沒(méi)有該標(biāo)識(shí)，這是很有用的。對(duì)單詞中的字母排序可以產(chǎn)生一個(gè)用于變位詞類(lèi)的標(biāo)識(shí)。其他標(biāo)識(shí)通過(guò)排序給出。然后使用一個(gè)計(jì)數(shù)來(lái)代表重復(fù)的次數(shù)（于是標(biāo)識(shí)“mississippi”可以寫(xiě)成“i4m1p2s4”或?qū)?省略——“i4mp2s4”）。也可以使用一個(gè)包含26個(gè)整數(shù)的數(shù)組來(lái)標(biāo)識(shí)每個(gè)字母出現(xiàn)的次數(shù)。標(biāo)識(shí)的其他應(yīng)用包括：美國(guó)聯(lián)邦調(diào)查局用來(lái)索引指紋的方法，以及用來(lái)識(shí)別讀音相同但是拼寫(xiě)不同的名字的Soundex啟發(fā)式方法：

Knuth⑧在其The Art of Computer Programming, Volume 3: Sorting and Sear ching⑨一書(shū)的第6章描述了Soundex方法。

問(wèn)題定義。第1章指出確定用戶(hù)的真實(shí)需求是程序設(shè)計(jì)的根本。本章的中心思想是問(wèn)題定義的下一步：使用哪些基本操作來(lái)解決問(wèn)題？在本章的每個(gè)例子中，啊哈！靈機(jī)一動(dòng)都定義了一個(gè)新的基本操作使得問(wèn)題得到簡(jiǎn)化。

問(wèn)題解決者的觀(guān)點(diǎn)。優(yōu)秀程序員都有點(diǎn)懶：他們坐下來(lái)并等待靈機(jī)一動(dòng)的出現(xiàn)而不急于使用最開(kāi)始的想法編程。當(dāng)然，這必須通過(guò)在適當(dāng)?shù)臅r(shí)候開(kāi)始寫(xiě)代碼來(lái)加以平衡。真正的技能就在于對(duì)這個(gè)適當(dāng)時(shí)候的把握，這只能來(lái)源于解決問(wèn)題和反思答案所獲得的經(jīng)驗(yàn)。

總結(jié)

以上是生活随笔為你收集整理的《编程珠玑（第2版•修订版）》—第2章2.5节原理的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。