《算法基礎：打開算法之門》一3.2 選擇排序

本節書摘來自華章出版社《算法基礎：打開算法之門》一書中的第3章，第3.2節，作者 ［美］托馬斯 h 科爾曼（thomas h cormen），更多章節内容可以通路雲栖社群“華章計算機”公衆号檢視

現在讓我們将注意力轉向排序：重排數組中的所有元素——也稱為重排數組——以便每個元素小于或者等于它的後繼。我們要看到的第一種排序算法是選擇排序，這是我能想到的最簡單的算法，在設計一個排序算法時，我最先能想到的就是選擇排序，雖然它遠遠不是最快的算法。

下面我們用依據作者名字對書架上的書排序這個例子來說明選擇排序是如何運作的。從左向右查找整個書架，并且找到作者名字最先在字母表中出現的書籍。假定這本排序在字母表中最前的書籍是由louisa may alcott所寫的（如果書架上包含由該作者所寫的兩本或者兩本以上的書籍，選擇它們中的任意一本）。将這個位置上的書籍和初始時位于位置1上的書籍進行調換。32現在位于位置1上的書籍是作者名字最先在字母表中出現的書籍。現在沿着書架從左向右查找，查找從第2個位置到第n個位置上的書籍中最先在字母表中出現的書籍。并假定這本書是由jane austen所寫的。将這本書與位于第2個位置的書籍進行調換，進而使得現在位于第1個位置和第2個位置上的書籍同時也是按照字母表排序中的位于最前面的第1個、第2個書籍。同理操作，得到位置3上應該放置的書籍，等等。一旦在位置n-1處放置了正确的書籍（可能是由hgwells所寫的書），那麼我們就完成操作了，因為這時僅僅就剩下一本書了（比如說，由oscar wilde所寫的書），并且它就位于它本身應該放置的第n個位置處。

為了将這個方法轉換成一個計算機算法，可以将書架看作是一個數組，所有的書看作是數組中的所有元素。下面是這個程式。

在a［in］中查找最小的元素相當于線性查找的變體。首先聲明a［i］是目前所看到的子數組中最小的元素，然後掃描子數組的剩餘部分，每當發現有一個元素小于目前最小的元素時，我們就更新最小元素的索引。下面是重定義的程式。

該程式有個“嵌套”循環，即第1b步中的循環嵌套在第1步中。對于外層循環的每次疊代，内層循環會執行它的循環體内的所有循環。注意内層循環的初始值j依賴于外層循環的目前值i。下圖表明了選擇排序在一個包含6個元素的數組中是如何進行排序的：

左上方是初始數組，每步展示了經過外層循環的一次疊代後的結果。灰色陰影的元素是目前得到的排好序的子數組。如果你想使用循環不變式來證明selectionsort程式能正确地實作排序操作，那就需要對每個循環進行證明。程式太簡單，我們不再證明其正确性，循環不變式如下：第1步中的每次循環疊代開始時，子數組a［1i-1］儲存着整個數組a的前i-1個有序排列的最小元素。第1b步中的每次循環疊代開始時，a［smallest］中存放着子數組a［ij-1］中的最小元素。selectionsort的運作時間是多少？我們将證明它是Θ（n2）。關鍵是分析出内層循環執行了多少次疊代，其中每次疊代需要花費Θ（1）時間。（這裡，因為在每次疊代中對smallest的指派操作可能發生也可能不會發生，是以Θ符号的下界和上界中的常數因子可能是不同的。）讓我們基于外部循環中循環變量i的值計算疊代的次數。當i等于1時，内層循環中j從2變化到n，共執行n-1次。當i等于2時，内層循環中j從3到n，共執行n-2次。外層循環中i值每增加1，那麼内層循環執行次數會減少1次。總結可得，内層循環每次執行n-i次。在外層循環的最後一次疊代中，當i等于n-1時，内層循環僅僅執行1次。是以内層循環疊代的總數是（n-1）+（n-2）+（n-3）+…+2+1，34這就是一個等差數列求和。根據等差數列的基本公式：對于任意非負整數k有

用n-1代替k，我們看到内層循環疊代的總次數是(n-1)n/2，即(n2-n)/2。使用漸近符号來省略低階項(-n)和常數因子(1/2)，那麼我們就可以稱内層循環的總次數是Θ（n2）。是以，selectionsort的運作時間是Θ（n2）。注意該運作時間能夠覆寫所有情況。無論實際的元素值是什麼，内層循環均會執行Θ（n2）次。下面用另一種不使用等差數列的方法來證明運作時間是Θ（n2）。我們将分别證明運作時間是o（n2)和Ω(n2)，将漸近上界和漸近下界聯合考慮就會得到Θ（n2）。為了證明運作時間是o（n2)，我們觀察發現外部循環的每次疊代對應的内層循環最多執行n-1次，而每次内層循環的疊代需花費常量時間，故外層循環的每次疊代需花費o（n)時間。由于外部循環疊代n-1次，即也是o（n)，故内層循環需要花費的總運作時間是o（n)乘以o（n)，即o（n2)。為了證明運作時間是Ω(n2)，我們觀察發現在外層循環的前n/2次疊代中，每個内層循環至少疊代n/2次，那麼總執行次數至少為n/2乘以n/2，即n2/4次。由于每個内層循環花費常量時間，是以我們證明出了運作時間至少是n2/4的常數倍，即為Ω(n2)。最後總結一下關于選擇排序的兩個結論。首先，我們看到漸近運作時間為Θ（n2），這是我們觀察到的最壞的排序算法。第二，如果認真觀察選擇排序是如何運作的，你将發現Θ（n2）的運作時間來自于第1bi步中的比較操作。但是移動元素的次數僅僅是Θ（n），因為第1c步僅僅執行了n-1次。如果移動元素相當耗時——或者它們所占空間很大或者它們儲存在一個存儲較慢的裝置（例如磁盤）中——那麼選擇排序可能是一個合适的算法。