通俗易懂講解 選擇排序

選擇排序介紹

選擇排序(Selection sort)是一種簡單直觀的排序演算法。其基本思想是：首先在未排序的數列中找到最小(or最大)元素，然後將其存放到數列的起始位置；接著，再從剩餘未排序的元素中繼續尋找最小(or最大)元素，然後放到已排序序列的末尾。以此類推，直到所有元素均排序完畢。

上面的說法可能還有點抽象，沒關係，下面讓我們用圖來說明一切，相信大家肯定能看懂和理解的。

圖解選擇排序

以數列{20,40,30,10,60,50}為例，演示其選擇排序過程(如下圖)。

排序流程如下：

第1趟：i=0。找出a[1...5]中的最小值a[3]=10，然後將a[0]和a[3]互換。 數組變化：20,40,30,10,60,50 -- > 10,40,30,20,60,50

第2趟：i=1。找出a[2...5]中的最小值a[3]=20，然後將a[1]和a[3]互換。 數組變化：10,40,30,20,60,50 -- > 10,20,30,40,60,50

第3趟：i=2。找出a[3...5]中的最小值，由於該最小值大於a[2]，該趟不做任何處理。

第4趟：i=3。找出a[4...5]中的最小值，由於該最小值大於a[3]，該趟不做任何處理。

第5趟：i=4。交換a[4]和a[5]的數據。 數組變化：10,20,30,40,60,50 -- > 10,20,30,40,50,60

選擇排序代碼

根據上面流程，不難寫出選擇排序的代碼實現，此處是按升序排列。

/* * 選擇排序 * n * 參數說明： n * a -- 待排序的數組 n * n -- 數組的長度 n */n nvoid select_sort(int a[], int n)n{n int i; // 有序區的末尾位置n int j; // 無序區的起始位置n int min; // 無序區中最小元素位置nn for(i=0; i<n; i++)n {n min=i;nn //找"a[i+1]..a[n]"之間最小元素，並賦給minn for(j=i+1; j<n; j++)n {n if(a[j] < a[min])n min=j;n }nn //若min!=i，則交換 a[i] 和 a[min]。n //交換後，保證了a[0]..a[i]之間元素有序。n if(min != i)n swap(a[i], a[min]);n }n}n

時間複雜度和穩定性

選擇排序的時間複雜度是 ：假設被排序的數列中有N個數。遍歷一趟的時間複雜度是O(N)，需要遍歷多少次呢？N-1次因此，選擇排序的時間複雜度是 。

選擇排序是穩定的演算法，它滿足穩定演算法的定義：假設在數列中存在a[i]=a[j]，若在排序之前，a[i]在a[j]前面；並且排序之後，a[i]仍然在a[j]前面。則這個排序演算法是穩定的！

更多文章見本文公眾號：碼農有道

版權所有！

推薦閱讀：