之前涉及的堆排序就是选择排序的一种,先进行选择。
基本选择排序:
最简单,也是最没用的排序算法,时间复杂度高并且还是不稳定的排序方法,项目中很少会用。
过程:
在一个长度为 N 的无序数组中,第一次遍历 n-1 个数找到最小的和第一个数交换。
第二次从下一个数开始遍历 n-2个数,找到最小的数和第二个数交换。
重复以上操作直到第 n-1 次遍历最小的数和第 n-1 个数交换,排序完成。
特点:如果挨个进行选择那么效率太慢。
算法优化:
默认开始的数是最大值最小值。比他大就更新,比他小也更新最大最小就可以了
注意一下这种情况:
当maxi和begin重合的时候交换之后maxi就被换走了,所以就需要使mini赋给maxi.
void SelectSort(int* a, int n)
{//数组需要使用地址形式。。假设一共有n个数据int begin = 0, end = n - 1;while (begin < end)//使用的是下标形式{int mini = begin, maxi = begin;for (int i = begin + 1; i <= end; ++i)//从第2个开始{if (a[i] > a[maxi]){maxi = i;}if (a[i] < a[maxi]){mini = i;} }Swap(&a[begin], &a[mini]);
if(maxi=begin)
maxi=mini;Swap(&a[end], &a[mini]);begin++;end--;}
}