直接选择排序是排序中比较简单的排序,同时也是时间复杂度不是很优的排序。
本文主要讲解直接选择排序的优化版本。
我们经过一次遍历直接将该数列中最大的和最小的值挑选出来,如果是升序,就将最小的和首元素进行交换,最大的与尾元素进行交换。然后将首部元素++,尾部元素--,重新遍历再次选择次大的和次小的。以此类推。
按照上面的思路会遇到一些特殊情况,造成排序的失败。
比如说我们先将最大的值赋给尾部元素,如果最大的值正好在头部元素,而最小的值恰好在尾部元素,这样就导致把最大的元素赋给尾部元素时,会把尾部本来的最小值覆盖掉,造成排序的失败。
为了解决这种情况,我们只需要将尾部元素提前存储好就欧克拉~
void SelectSort(int* a, int n)
{
int begin = 0;
int end = n - 1;
while (begin <= end)
{
int maxi = begin, mini = begin;
for (int i = begin + 1; i < end + 1; i++)
{
//找出最大值和最小值的下标
if (a[i] > a[maxi])
maxi = i;
if (a[i] < a[mini])
mini = i;
}
Swap(&a[begin], &a[mini]);
//max如果被换走,就修正以下
if (maxi == begin)
maxi = mini;
Swap(&a[end], &a[maxi]);
begin++;
end--;
}
}
这也是一个等差数列,所以时间复杂度就是O(N^2)。
显然这并不是一个优的排序算法。