Like Share Discussion Bookmark Smile

J.J. Huang   2020-03-07   排序演算法   瀏覽次數:

排序演算法 | 選擇排序

選擇排序(Selection sort)是一種簡單直觀的排序演算法。它的工作原理如下。首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然後,再從剩餘未排序元素中繼續尋找最小(大)元素,然後放到已排序序列的末尾。以此類推,直到所有元素均排序完畢。

選擇排序的主要優點與資料移動有關。如果某個元素位於正確的最終位置上,則它不會被移動。選擇排序每次交換一對元素,它們當中至少有一個將被移到其最終位置上,因此對n個元素的表進行排序總共進行至多n-1次交換。在所有的完全依靠交換去移動元素的排序方法中,選擇排序屬於非常好的一種。

使用選擇排序為一列數字進行排序的過程:

選擇排序的範例動畫。紅色表示目前最小值,黃色表示已排序序列,藍色表示目前位置。

實作範例(Java)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
@Test
public void SelectionSort() {
    int[] arr = { 3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48 };
    for (int i = 0; i < arr.length - 1; i++) {
        int index = i;
        for (int j = 1 + i; j < arr.length; j++) {
            if (arr[j] < arr[index]) {
                index = j;// 保存最小元素的下標
            }
        }
        // 此時已經找到最小元素的下標
        // 將最小元素與前面的元素交換
        int temp = arr[index];
        arr[index] = arr[i];
        arr[i] = temp;
    }
    System.out.println(Arrays.toString(arr));
}

結果:

1
[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

實現也非常的簡單,首先在外循環裡定義了一個index變量儲存i的值,這是為了避免重複地比較,因為在每一輪的比較結束後,前i個元素是已經排好序的,所以無需再次比較,只需從i開始即可。後面的比較都是基於index位置的元素進行比較,倘若比較完後index位置的元素是最小值,那就無需交換,不動即可。而如果找到了比index位置的元素更小的元素,那就將該元素的索引賦值給index,然後繼續比較,直到比較完成,比較完成之後得到的index即為數組中的最小值,那此時只需要將index位置的元素和i位置的元素交換即可。


註:以上參考了
維基百科-選擇排序
演算法筆記
程式员必须掌握的核心算法有哪些?
程式员那些必须掌握的排序算法(上)
程式员那些必须掌握的排序算法(下)