Selection Sort - 選擇排序

核心：不斷地選擇剩餘元素中的最小者。
1. 找到陣列中最小元素並將其和陣列第一個元素交換位置。
2. 在剩下的元素中找到最小元素並將其與陣列第二個元素交換，直至整個陣列排序。

性質：
* 比較次數=(N-1)+(N-2)+(N-3)+…+2+1~N^2/2
* 交換次數=N
* 運行時間與輸入無關
* 數據移動最少

下圖來源為 File:Selection-Sort-Animation.gif - IB Computer Science

Implementation

Python

  1. #!/usr/bin/env python
    2.   3.   4. def selectionSort(alist):
    5.     for i in xrange(len(alist)):
    6.         print(alist)
    7.         min_index = i
    8.         for j in xrange(i + 1, len(alist)):
    9.             if alist[j] < alist[min_index]:
    10.                 min_index = j
    11.         alist[min_index], alist[i] = alist[i], alist[min_index]
    12.     return alist
    13.   14. unsorted_list = [8, 5, 2, 6, 9, 3, 1, 4, 0, 7]
    15. print(selectionSort(unsorted_list))

Java

  1. public class Sort {
    2.     public static void main(String[] args) {
    3.         int unsortedArray[] = new int[]{8, 5, 2, 6, 9, 3, 1, 4, 0, 7};
    4.         selectionSort(unsortedArray);
    5.         System.out.println("After sort: ");
    6.         for (int item : unsortedArray) {
    7.             System.out.print(item + " ");
    8.         }
    9.     }
    10.   11.     public static void selectionSort(int[] array) {
    12.         int len = array.length;
    13.         for (int i = 0; i < len; i++) {
    14.             for (int item : array) {
    15.                 System.out.print(item + " ");
    16.             }
    17.             System.out.println();
    18.             int min_index = i;
    19.             for (int j = i + 1; j < len; j++) {
    20.                 if (array[j] < array[min_index]) {
    21.                     min_index = j;
    22.                 }
    23.             }
    24.             int temp = array[min_index];
    25.             array[min_index] = array[i];
    26.             array[i] = temp;
    27.         }
    28.     }
    29. }

C++

  1. void selectionSort(vector<int> & arr){
    2.     int min_idx = 0;
    3.     for(int i = 0; i < arr.size(); i++){
    4.         min_idx = i;
    5.         for(int j = i + 1; j < arr.size(); j++){
    6.             if (arr[j] < arr[min_idx])
    7.                 min_idx = j;
    8.         }
    9.         std::swap(arr[i], arr[min_idx]);
    10.     }
    11. }

Reference

• 選擇排序 - 維基百科，自由的百科全書
• The Selection Sort — Problem Solving with Algorithms and Data Structures