[数据结构]排序之 直接选择排序

1 基本思想：

每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的

数据元素排完 。

2 直接选择排序 :

在元素集合 array[i]--array[n-1] 中选择关键码最大 ( 小 ) 的数据元素

若它不是这组元素中的最后一个 ( 第一个 ) 元素，则将它与这组元素中的最后一个（第一个）元素交换

在剩余的 array[i]--array[n-2] （ array[i+1]--array[n-1] ）集合中，重复上述步骤，直到集合剩余 1 个元素

// 选择排序
void SelectSort(int* a, int n)
{int left = 0;int right = n - 1;while (left < right){int mini = left, maxi = left;//记录下标for (int i = left+1; i <= right; i++){if (a[i] < a[mini]){mini = i;}if (a[i] > a[maxi]){maxi = i;}}Swap(&a[left], &a[mini]);// 检查最大值位置是否被改变if (maxi == left) {maxi = mini;}Swap(&a[right], &a[maxi]);++left;--right;}
}

为什么要在两个Swap之间写一个if？

考虑这样一种情况：当  left  位置的元素就是当前未排序部分的最大值时，在第一次交换  a[left]  和  a[mini]  之后，原本  maxi  指向的最大值元素已经被交换到了  mini  位置，而时  maxi  仍然指向原来的  left  位置，所以在进行第二次交换  a[right]  和  a[maxi]  时，实际上交换的并不是最大值，从而导致排序结果出错。

直接选择排序的特性总结：

1. 直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用

2. 时间复杂度： O(N^2)  最坏情况和最好情况都是 O(N^2),之前的序列对排序没有影响，所以直接选择排序很烂，基本不会用

3. 空间复杂度： O(1)

4. 稳定性：不稳定