排序算法係列之選擇排序

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

基本思想

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

排序過程：

對於一組關鍵字{K₁,K₂,…,K_n}，首先從K₁,K₂,…,K_n中選擇最小值，假如它是 K_z，則將K_z與 K₁對換；然後從K₂，K₃，… ，K_n中選擇最小值 K_z，再將K_z與K₂對換。如此進行選擇和調換n-2趟，第(n-1)趟，從K_n-1、K_n中選擇最小值 K_z將K_z與K_n-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;
        }
    }
}

算法性能分析

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