[数据结构]排序之 直接选择排序
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.
稳定性：不稳定