Sorting Algorithm

程式的基本功

Selection Sort

　　也是一種最簡單基本、容易理解的排序演算法。
基本概念：利用最直觀的方法，將未排序的資料中找出最大(最小)的元素插入至已排序好的數列中的最右(左)端。
也就是自第i筆到第n筆中挑出最大(最小)的元素，再與第i筆swap。(i=1 to (n-1)作(n-1)回合)

Principle

  • 通常不會使用額外的數列記錄已排序好的數列。
    • 　
  • 將數列分成兩部分：未排序及已排序。

    • Complexity

    Time complexity:
    從比較次數來看
    Best.Worst.Average case皆為O(n2)。
    因比較次數=(n-1)+(n-2)+...+1
    　　　　　=n(n-1)/2次 => O(n2)。

    Space complexity:
    　　O(1)。

    運算流程

    1. 從未排序的數列中找到最大(小)的元素。。
    2. 將此元素取出並加入至已排序的數列的最右(左)端。
    3. 重複以上動作1->2直到未排序部分的數列全部處理完成。

    Stable vs. Unstable sort

    Unstable。
    ex: Input:5, 5*, 1
    　Output可能為 1, 5, 5* or 1, 5*, 5。

    簡易code

    SelectSort(list,n)
    { for i=1 to (n-1) do
    　{ min = i;
    　　for j=(i+1) to n do
    　　　if list[j]<list[min] then
    　　　　min = j;
    　　if (min != i)then swap(list[min], list[i]);
    　}
    }