簡單選擇排序

簡單選擇排序

（1）算法思想：

假定前i-1個元素已經有序（升序），則從第i ~ n個元素中選出最小的與現在的第i個元素交換。

（2）僞代碼：

SelectSort(int a[], int n)

{

        for (int i=0; i<n-1; i++)

        {

                int smallest = i;

                for (int j=i+1; j<n; j++)

                {

                         if (a[j]<a[smallest])

                                 smallest = j;

                }

                swap(a[i], a[smallest])

        }

}

（3）分析：

1）不穩定 2）空間代價：Θ(1) 3）時間代價： 比較次數：Θ(n^2) 交換次數：n-1，如果算上swap，應該是3(n-1)，總的來說是Θ(n) 總代價：Θ(n^2)