排序算法之選擇排序

簡單選擇排序也是直接選擇排序

基本思想

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

排序過程：

    對于一組關鍵字{K1,K2,…,Kn}， 首先從K1,K2,…,Kn中選擇最小值，假如它是 Kz，則将Kz與 K1對換；然後從K2，K3，… ，Kn中選擇最小值 Kz，再将Kz與K2對換。如此進行選擇和調換n-2趟，第(n-1)趟，從Kn-1、Kn中選擇最小值 Kz将Kz與Kn-1對換，最後剩下的就是該序列中的最大值，一個由小到大的有序序列就這樣形成。

【例】下圖是一個有5個關鍵字{3,4,1,5,2}的簡單選擇排序過程的示意圖。

算法示範

1.對初始關鍵字為49、38、65、97、76、13、27和49的檔案進行直接選擇排序的過程

2.圖檔示範：

算法實作（C語言）

void select_sort(int *a, int n)
{
    register int i, j, min, t;
    for(i = 0; i < n - 1; i ++)
    {
        min = i;
        //查找最小值
        for(j = i + 1; j < n; j ++)
            if(a[min] > a[j])
                min = j;
        //交換
        if(min != i)
        {
            t = a[min];
            a[min] = a[i];
            a[i] = t;
        }
    }
}      

算法性能分析

   選擇排序的交換操作介于和次之間。選擇排序的比較操作為次之間。選擇排序的指派操作介于和次之間。比較次數O(n^2),比較次數與關鍵字的初始狀态無關，總的比較次數N=(n-1)+(n-2)+...+1=n*(n-1)/2。 交換次數O(n),最好情況是，已經有序，交換0次；最壞情況是，逆序，交換n-1次。 交換次數比冒泡排序少多了，由于交換所需CPU時間比比較所需的CPU時間多，n值較小時，選擇排序比冒泡排序快。（直接）選擇排序是一個就地排序，直接選擇排序是不穩定的。