【数据结构】直接选择排序

1.选择排序

1.1 基本思想：

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

数据元素排完 。

1.2 直接选择排序：

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

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

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

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

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

2. 时间复杂度：O（N^2）

3. 空间复杂度：O（1）

4. 稳定性：不稳定

这里我们做一下改进，遍历一次数组选出最大和最小的数，最小的数放最左边，最大的数放最右边，排成升序

实现步骤：

1.设置两个存放下标的变量 start，end；

2.遍历数组中的元素，找出当前区间最小和最大数据的下标；

3.数组中最大和最小的数据放到数组两头

4.start++，end--，如果 start < end 就一直进行

// 选择排序 
void SelectSort(int* a, int n)
{int start = 0;int end = n - 1;while ( start < end){int mini, maxi;mini = maxi = start;for (int i = start+1; i <= end; i++){if (a[mini] > a[i]){mini = i;}if (a[maxi] < a[i]){maxi = i;}}swap(&a[start], &a[mini]);//如果maxi和start的位置重叠，则maxi的位置需要修正if (maxi == start){maxi = mini;}swap(&a[end], &a[maxi]);end--;start++;}
}