排序算法系列之选择排序

简单选择排序也是直接选择排序

基本思想

选择排序(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值较小时，选择排序比冒泡排序快。（直接）选择排序是一个就地排序，直接选择排序是不稳定的。