之前涉及的堆排序就是选择排序的一种,先进行选择。
基本选择排序:
最简单,也是最没用的排序算法,时间复杂度高并且还是不稳定的排序方法,项目中很少会用。
过程:
在一个长度为 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--;
}
}