本文內(nèi)容借鑒一本我非常喜歡的書——《數(shù)據(jù)結(jié)構(gòu)與算法圖解》。學(xué)習(xí)之余，我決定把這本書精彩的部分摘錄出來與大家分享。???
目錄
寫在前面
1.選擇排序
2.選擇排序?qū)崙?zhàn)
3.選擇排序的實現(xiàn)
4.選擇排序的效率
5.忽略常數(shù)
6.大O的作用
7.總結(jié)
?
?文章來源地址http://www.zghlxwxcb.cn/news/detail-622635.html
寫在前面
大 O 是一種能夠比較算法效率，并告訴我們在特定環(huán)境下應(yīng)采用何種算法的偉大工具。但我們不能完全依賴于它。
因為有時候即使兩種算法的大 O 記法完全一樣，但實際上其中一個比另一個要快得多。
本章我們就來學(xué)習(xí)如何分辨那些效率貌似一樣的算法，從而選出較快的那個。
1.選擇排序
上一章分析了冒泡排序算法，其效率是 O(N^2 )?，F(xiàn)在我們再來探索另一種排序算法，選擇排
序，并將它跟冒泡排序?qū)Ρ纫幌隆?/p>
選擇排序的步驟如下。
(1) 從左至右檢查數(shù)組的每個格子，找出值最小的那個。在此過程中，我們會用一個變量來記住檢查過的數(shù)字的最小值（事實上記住的是索引，但為了看起來方便，下圖就直接寫出數(shù)值）。如果一個格子中的數(shù)字比記錄的最小值還要小，就把變量改成該格子的索引，如圖所示。
(2) 知道哪個格子的值最小之后，將該格與本次檢查的起點交換。第 1 次檢查的起點是索引 0，
第 2 次是索引 1，以此類推。下圖展示的是第一次檢查后的交換動作。
(3) 重復(fù)第(1) (2)步，直至數(shù)組排好序。?
2.選擇排序?qū)崙?zhàn)
以數(shù)組 [4,2,7,1,3] 為例，步驟如下。
開始第 1輪檢查。
首先讀取索引 0。根據(jù)此算法的定義，它是目前遇到的最小值（因為現(xiàn)在只檢查了一個格子），于是記下其索引。
第 1步：將索引 1的值 2與目前的最小值 4進(jìn)行比較。
2比 4還要小，于是將目前的最小值改為 2。
第 2步：再與下一個值做比較。因為 7大于 2，所以最小值還是 2。
第 3步：將 1和目前的最小值做比較。?
1比 2還要小，于是目前的最小值更新為 1。
第 4步：比較 3和目前的最小值 1。因為現(xiàn)在已經(jīng)走到數(shù)組盡頭了，所以可以斷定 1是整個
數(shù)組的最小值。?
第 5步：本次檢查的起點是索引 0，不管那里的值是什么，我們都應(yīng)該將最小值 1換到那里。
現(xiàn)在 1就排到正確的位置上了。
可以開始第 2輪檢查了。?
準(zhǔn)備工作：因為索引 0的值已符合其排位，所以這一輪從下一個格子開始，即索引 1，其值為 2，也是目前本輪所遇到的最小值。
第 6步：將 7跟目前的最小值 2進(jìn)行比較。因為 2小于 7，所以最小值仍為 2。
?第 7步：將 4跟目前的最小值 2進(jìn)行比較。因為 2小于 4，所以最小值仍為 2。
第 8步：將 3跟目前的最小值 2進(jìn)行比較。因為 2小于 3，所以最小值仍為 2。?
又走到數(shù)組盡頭了。本輪不需要做任何交換，2已在其正確位置上。于是第 2輪檢查結(jié)束，現(xiàn)在數(shù)組如下圖所示。?、
開始第 3輪檢查。?
準(zhǔn)備工作：從索引 2起，其值為 7。于是本輪目前最小值為 7。
第 9 步：比較 4 與 7。
將 4 記為目前的最小值。?
第 10 步：遇到 3，它比 4 還小。
于是 3 成了目前的最小值。
第 11 步：到數(shù)組盡頭了，將 3 跟本輪起點 7 進(jìn)行交換。?
于是 3 排到正確位置上了。?
雖然我們可以看到現(xiàn)在整個數(shù)組都有序了，但計算機(jī)是看不到的，它只會繼續(xù)第 4輪檢查。
準(zhǔn)備工作：此輪檢查從索引 3開始，其值 4是目前的最小值。
第 12步：比較 4和 7。?
4仍為最小值，而且它也處于本輪起點，因此無須任何交換。
因為最后一個格子左側(cè)的那些值都已在各自的正確位置上，所以最后一格也必然正確，于是排序結(jié)束。
3.選擇排序的實現(xiàn)
下面是用C語言實現(xiàn)的選擇排序：
void SelectSort(int arr[], int n)//升序
{
for (int i = 0; i < n-1; i++) //n個數(shù)，只需排好n-1個，剩下的一個自然在正確的位置上
{
int min = i; //用min來記錄最小值的索引（下標(biāo)）
for (int j = i+1; j < n; j++) //從i索引的后一個開始比較
{
if (arr[j] < arr[min])
{
min = j; //找到比自己小的數(shù)的索引，并成為它
}
}
if (min != i) //如果min的值改變，則與i處的值交換
{
int tmp = arr[i];
arr[i] = arr[min];
arr[min] = tmp;
}
}
}下面來進(jìn)行分析：
for (int i = 0; i < n-1; i++)?這個外層的循環(huán)代表每一輪檢查。在一輪檢查之初，我們會先記住目前的最小值的索引。
int min = i;因此每輪開始時 min?都會是該輪的起點索引 i 。
注意我們實際上記錄的是最小值的索引，而非最小值本身。于是，第 1 輪開始時最小值的索引是 0，到第 2 輪則是 1，以此類推。
for (int j = i+1; j < n; j++)這個內(nèi)層循環(huán)控制的是找出最小值的索引的過程。
if (arr[j] < arr[min])
{
min = j;
}循環(huán)內(nèi)逐個檢查數(shù)組未排序的格子，若遇到比之前記錄的本輪最小值還小的格子值，就將min更新為該格子的索引。
內(nèi)層循環(huán)結(jié)束時，會得到未排序數(shù)值中最小值的索引。
if (min != i)
{
int tmp = arr[i];
arr[i] = arr[min];
arr[min] = tmp;
}然后再看看這個最小值是否已在正確位置，即該索引是否等于 i 。如果不是，就將 i 所指的值與最小值交換。
4.選擇排序的效率
選擇排序的步驟可分為兩類：比較和交換。
若有 N個元素，就會有 (N -?1) + (N -?2) + (N -?3) + … + 1次比較。
但每輪的交換最多只有 1 次。如果該輪的最小值已在正確位置，就無須交換，否則要做 1 次交換。相比之下，冒泡排序在最壞情況（完全逆序）時，每次比較過后都要進(jìn)行 1 次交換。
下表為冒泡排序和選擇排序的并列對比。
從表中可以清晰地看到，選擇排序的步數(shù)大概只有冒泡排序的一半，即選擇排序比冒泡排序快一倍。?
5.忽略常數(shù)
但有趣的是，選擇排序的大 O記法跟冒泡排序是一樣的。
還記得我們說過，大 O記法用來表示步數(shù)與數(shù)據(jù)量的關(guān)系。所以你可能會以為步數(shù)約為 N^2的一半的選擇排序，其大 O會寫成 O(N ^2/ 2)，以表示 N個元素需要 N ^2?/ 2步。如下表所示。
但事實上，選擇排序的大 O記法為 O(N^2 )，跟冒泡排序一樣。這是因為大 O記法的一條重要
規(guī)則：
大 O 記法忽略常數(shù)。
6.大O的作用
盡管不能比較冒泡排序和選擇排序，大 O 還是很重要的，因為它能夠區(qū)分不同算法的長期增長率。當(dāng)數(shù)據(jù)量達(dá)到一定程度時，O(N)的算法就會永遠(yuǎn)快過 O(N^2 )，無論這個 O(N)實際上是O(2N)還是 O(100N)。
下圖為 O(N)和 O(N^2 )的對比。
這就是大 O 記法忽略常數(shù)的原因。大 O 記法只表明，對于不同分類，存在一臨界點，在這一點之后，一類算法會快于另一類，并永遠(yuǎn)保持下去。至于這個點在哪里，大 O并不關(guān)心。
因此，不需要寫成 O(100N)，歸類到 O(N)就好了。
7.總結(jié)
現(xiàn)在我們已經(jīng)掌握了一些非常強(qiáng)大的算法分析手法。我們能夠使用大 O去判斷各種算法的效率，即便兩種算法的大 O記法一樣，也知道如何對比它們。不過在對比算法時，還需要考慮一個重要因素。至今我們關(guān)注的都是最壞情況下算法會跑得多慢，但其實最壞情況并不總會發(fā)生。沒錯，我們遇到的大都是平均情況。下一章，我們會學(xué)習(xí)怎樣顧及所有情況。
文章來源：http://www.zghlxwxcb.cn/news/detail-622635.html
?
到了這里，關(guān)于『初階數(shù)據(jù)結(jié)構(gòu) ? C語言』⑤ - 選擇排序的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
