2.选择排序法（Selection Sort）
插入排序法（insertion sort）是一种稳定的排序算法，而选择排序法（selection sort）是一种不稳定的排序算法。
所谓排序的稳定性，评判标准是：值相等的两个数在排序前后的相对位置是否发生变化，如果保持原有相对顺序，则排序稳定，若原有顺序被破坏，则排序不稳定。
要了解选择排序法是否稳定，需要先了解选择排序作用的机理。假定有n个元素的数组A，用选择排序法对n个数进行排序，首先要找出数组A中的最小元素，与A[0]位置的元素对调位置，然后找出数组A中的次小元素，与A[1]位置的元素对调位置，以此类推。进行到第n-1个数时，排序就结束了，因为在最坏的情况下，最后一轮会对数组最后的两个元素进行比较，此后最后的元素必然是数组中最大的元素。
对于选择排序的不稳定性，举个例子：有一维数组a[6]={31,41,59,26,41,58}，其中有两个41，每个元素按序标记为：A31,B41,C59,D26,E41,F58.
如果使用插入算法，排序完成后，两个41的相对位置是不改变的，即：D26,A31,B41,E41,F58,C59.
如果采用选择算法，排序完成后，两个41的相对位置就被破坏了，即：D26,A31,E41,B41,F58,C59.
可以看到，本来应该排在前面的B41，经过选择排序之后，反而排到E41后面了，在现实应用中，是不允许这种情况发生的，所以说这种排序是不稳定的。
时间复杂度：最好和最差的情况之间，选择排序的交换操作介于 0 和 (n-1)次之间，赋值操作介于0和 3(n-1)次之间。比较次数与关键字的初始状态无关，总的比较次数N=(n-1)+(n-2)+...+1=n(n-1)/2，比较操作的时间复杂度为O(n2)。
最好的情况下，已经有序，交换0次；
最差的情况下，交换n-1次；
逆序情况下，交换n/2次。
总的来说，交换次数比冒泡排序少，由于交换所需CPU时间比比较所需的CPU时间多，所以当输入规模较小时，选择排序比冒泡排序快。因此，选择排序的时间复杂度为O(n2)，空间复杂度为O(1)。
空间复杂度(Space Complexity)：类似时间复杂度，空间复杂度用来描述一个算法运行时占用存储空间的情况，空间复杂度也可以表示为输入规模n的函数，也用O(*)表示。当一个算法的空间复杂度为一个常量，即占用存储空间不随被处理数据量n的大小而改变时，可表示为O(1)，当一个算法的空间复杂度与以2为底的n的对数成正比时，可表示为O(log2n)，当一个算法的空间复杂度与n成线性比例关系时，可表示为O(n).
代码实现（虽然用的C++，但还是习惯面向过程= =）：
#include <iostream>
using namespace std;
int Selection_Sort(int* arr, int length) {
int min;
int i, j;
int flag=0;
for (i = 0; i < length-1; i++) {
min = arr[i];
for (j = i + 1; j < length; j++) {
if (arr[j] < min) {
min = arr[j];
flag = j;
}
}
arr[flag] = arr[i];
arr[i] = min;
}
for (i = 0; i < length; i++) cout << arr[i] << " ";
return 0;
}
int main() {
int a[6] = { 31,41,59,26,41,58 };
Selection_Sort(a, 6);
return 0;
}另外，选择排序法其实可以分为：直接选择排序（Straight selection sort）、树形选择排序（Tree-type selection sort）以及堆排序（Heap sort）。
（1）直接选择排序：①基本思想：实现思想是每步从排序记录中选出排序码最小（最大）的记录，放在已排序记录序列的最后（前）；②算法特点：直接选择排序算法n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果。
（2）树形选择排序：①基本思想：其实现思想是保存先前比较的结果以减少比较次数，是一种不稳定的排序方法。首先对n个记录的关键字进行两两比较，然后在n/2个较小者之间再进行两两比较，如此重复，直至选出最小的记录为止。
（3）堆排序：①基本思想：堆排序是一种树形选择排序，是对直接选择排序的有效改进；②算法描述：从算法描述来看，堆排序需要两个过程，即建立堆和堆顶与堆的最后一个元素交换位置。所以堆排序有两个函数组成，一是建堆的渗透函数，二是反复调用渗透函数实现排序的函数；③算法特点：堆排序可通过树形结构保存部分比较结果，可减少比较次数。但由于建初始堆所需的比较次数较多，所以堆排序不适宜于记录数较少的文件。
