選擇排序 (Selection Sort)

選擇排序的原理是每次都在剩下的資料中找出最小的資料，將該資料丟到當前的正確位置。

歡迎參考 edX 上開授的 CS 50 課程示範影片:

也就是說將第 i 筆到第 n 筆資料中排出最小值，與第 i 筆資料做交換。

• 從 i = 1 到 n-1 ，作 n-1 回合
• 每回合自第 i 筆到第 n 筆中排出最小值，與第 i 筆資料做交換

虛擬碼

SelectionSort(A, n) //排序A[1]到A[n]
  for i = 0 to n-2 do
    min = i
    for j = i+1 to n-1 do
      if A[j] < A[min]
        min = j
      swap A[i] and A[min]

 

程式碼

void swap(int *a, int *b){
  int temp;
  temp = *a;
  *a = *b;
  *b= temp;
}

int selection_sort(int list[], int n){
  int i, j, min_id;
  for(i = 0; i<n-1; i++){
    min_id = i;
    for(j=i+1; j<n; j++){
      if (list[j] < list[min_id])
        min_id = j;
    }
    swap(&list[i], &list[min_id]); //送地址過去swap function
  }
};

int main(){
  int count, i;
  scanf("%d", &count);
  int list[count];
  printf("Numbers to be sorted: ");
  for(i = 0; i<count; i++){
    scanf("%d", &list[i]);
    printf("%d ", list[i]);
  }
  printf("\n");
  selection_sort(list, count);
  printf("Numbers Sorted: ");
  for(i = 0; i<count; i++){
    printf("%d ", list[i]);
  }
  return 0;
}

時間複雜度

無論 Average/Worst/Best Case 皆為 O(n²)

比較次數= (n-1) + (n-2) + … +1 = n(n-1)/2 次

 

空間複雜度: O(1)

需要一個額外的空間儲存暫存變數 temp 用來做資料交換用。

 

穩定性: UNSTABLE

選擇排序屬於不穩定排序──第 i 回合會將第 i 小的資料與第 i 個位置做交換。即使資料大小相同也會被交換。

Pass 0
------------------------- 
array index: [0] [1] [2] 
input data:   5   5*  3  

Pass 1: 
-------------------------
array index: [0] [1] [2]
input data:   3   5*  5

可以發現在第一回合過後，5* 從原本在 5 後面，跑到了 5 前面。