目录
前言
上期我们对插入排序中的直接插入排序和希尔排序进行了分析，我们了解了如何实现它们和它们的性能比较，知道了希尔排序是直接插入排序的优化。今天我们来学习选择排序。
什么是选择排序
百度百科中说：排序定义。所谓计算机中的排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。而排序算法则是一种能将一串数据依照特定的方式进行排列的一种算法。排序方式。利用所需重排记录的排序码的值的大小，按照升序或降序将原纪录的顺序重新安排。排序类别。内排序可以分为插入排序、选择排序、交换排序、归并排序以及分配排序。选择排序法是一种不稳定的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到全部待排序的数据元素排完。常见的选择排序可以分为直接选择排序、树状排序以及堆排序。今天我们说的就是直接选择排序
选择排序的实现
基本思想
首先在未排序的数组中找到最小元素，存放到排序数组的起始位置。
再从剩余未排序元素中继续寻找最小元素，然后放到已排序数组的末尾。
重复第二步，直到所有元素全部排序完毕。
具体实现代码
#include <stdio.h> //直接选择排序 void SelectSort(int* arr, int len) { int i = 0; int j = 0; //这里是它比较的趟数，就是每个元素都和后面的比较，找出最小值 //到最后一个元素的时候已经是有序的了所以就是len-1次 for (i = 0; i < len - 1; i++) { //把未处理的数组中第一个元素的下标假设为最小下标 int min = i; //找出无序数组中最小的元素 for (j = i + 1; j < len; j++) { //min下标的元素大于后面的元素 if (arr[min] > arr[j]) { //min跟换下标 min = j; } } //将无序数组中的第一个元素与真正最小值交换 int tmp = arr[min]; arr[min] = arr[i]; arr[i] = tmp; } } int main() { //待排序数组 int arr[] = { 2,3,1,0,4, 9,10,6,5 }; //直接选择排序 SelectSort(arr, sizeof(arr) / sizeof(arr[0])); //打印 int i = 0; for (i = 0; i < sizeof(arr) / sizeof(arr[0]); i++) { printf("%d ", arr[i]); } return 0; }
选择排序的原理
选择排序法的第一层循环从起始元素开始选到倒数第二个元素，主要是在每次进入的第二层循环之前，将外层循环的下标赋值给临时变量，接下来的第二层循环中，如果发现有比这个最小位置处的元素更小的元素，则将那个更小的元素的下标赋给临时变量，最后，在二层循环退出后，如果临时变量改变，则说明，有比当前外层循环位置更小的元素，需要将这两个元素交换 。这里我们以代码中的数组为例：
第一次：我们可以将数组中第一个元素暂时设为最小值，然后与后面的元素相比较，3大于最小值2跳过，1小于2则最小值给到2，再和后面比较发现后面的元素都大于1.这时就将1与数组第一个元素交换。第二次：我们将第二个元素为最小值与后面的元素比较，发现3大于2，则最小值就是2，2再与后面的元素比较发现没有比他小的，则将2放在已经排好数组的后面。第三次：假设最小值为3，发现后面的都比他大，不变。第4次：假设4为最小值，发现后面的元素都大于它，不变。第5次：假设9为最小值，发现后面的元素10大于它，不变。6小于它，则最小值为6，再比较，发现5小于6，则6为最小值，将6放到有序数组的后面，后面的步骤重复如此，直到排序成功。
选择排序的性能
时间复杂度
选择排序的交换操作介于 0 和 (n - 1） 次之间。选择排序的比较操作为 n (n - 1） / 2 次之间。选择排序的赋值操作介于 0 和 3 (n - 1） 次之间。比较次数O(n^2），比较次数与关键字的初始状态无关，交换次数O(n），最好情况是，已经有序，交换0次；最坏情况交换n-1次，逆序交换n/2次。交换次数比冒泡排序少多了，由于交换所需CPU时间比比较所需的CPU时间多，n值较小时，选择排序比冒泡排序快。其中直接选择排序的时间复杂度为O（n*n），空间复杂度为O（1）。树形选择排序的时间复杂度为O（nlog2n），空间复杂度为O（n）。堆排序的平均时间复杂度为O（nlog2n），效率高，但是实现相对复杂，空间代价为O（1）。
稳定性
选择排序是给每个位置选择当前元素最小的，比如给第一个位置选择最小的，在剩余元素里面给第二个元素选择第二小的，依次类推，直到第n-1个元素，第n个元素不用选择了，因为只剩下它一个最大的元素了。那么，在一趟选择，如果一个元素比当前元素小，而该小的元素又出现在一个和当前元素相等的元素后面，那么交换后稳定性就被破坏了。举个例子，序列5 8 5 2 9，我们知道第一遍选择第1个元素5会和2交换，那么原序列中两个5的相对前后顺序就被破坏了，所以选择排序是一个不稳定的排序算法 。
改进
二元选择排序
改进思路： 简单选择排序，每趟循环只能确定一个元素排序后的定位。根据之前冒泡排序的经验，我们可以考虑改进为每趟循环确定两个元素（当前趟最大和最小记录）的位置,从而减少排序所需的循环次数。改进后对n个数据进行排序，最多只需进行[n/2]趟循环即可。
堆排序
堆排序是一种树形选择排序，是对直接选择排序的有效改进。具体的分析我们留到后面讲堆排序时再详细说明。
这些改进再后面的文章会再次提到的。
