【基本思想】

简单选择排序是选择类排序中简单的一种，其基本思想是：第 $i$ 趟排序在待排序列 $a[i]$~$a[n]$ 中选取关键码最小的记录，这样每一趟确定第 $i$ 个元素，$n-1$ 趟即可排序完成

简单选择排序的具体的排序过程如下：

1）将整个记录序列划分为有序区和无序区，初始时有序区为空，无序区含有待排序的所有记录

2）在第 $i$ 趟中，在无序区选择关键码最小的记录，将其与有序区中的第 $i$ 个元素交换，使得有序区扩展一个记录，同时无序区减少了一个记录

3）不断重复步骤 2），直到无序区剩下一个记录为止

简单选择排序的宏观排序过程如下

【实例】

以数列 $\{7,4,5,9,8,2,1\}$ 为例，演示简单选择排序过程：

【性能分析】

简单选择排序适用于顺序存储、链式存储方式，在第 $i$ 趟找到最小元素后，会与第 $i$ 个元素交换，这可能会导致第 $i$ 个元素与其含有相同关键字元素的相对位置发生改变，因此其是一种不稳定排序算法

简单选择排序在排序过程中，仅需常数个辅助空间，作为待插入记录的暂存单元，因此其空间复杂度为

$O(1)$

由于每个元素移动次数不会超过 $3(n-1)$ 次，因此，在最好情况下，仅需要移动 $0$ 次，但元素间比较的次数与序列初始状态无关，始终为 $\frac{n(n-1)}{2}$ 次，因此总时间复杂度始终为

$O(n^2)$

【实现】

void selectSort (int a[], int n) {
    for (int i = 1; i <= n - 1; i++) { //n-1趟选择
        int index = i; //当前有序区索引位置
        for (int j = i + 1; j <= n; j++) //在无序区选取最小的记录
            if(a[index] > a[j])
                index = j;
        if(index != i)
            swap(a[i],a[index]);
    }
}