手撕排序之直接选择排序

前言：

直接选择排序是排序中比较简单的排序，同时也是时间复杂度不是很优的排序。

思想：

本文主要讲解直接选择排序的优化版本。

我们经过一次遍历直接将该数列中最大的和最小的值挑选出来，如果是升序，就将最小的和首元素进行交换，最大的与尾元素进行交换。然后将首部元素++，尾部元素--，重新遍历再次选择次大的和次小的。以此类推。

注意：

按照上面的思路会遇到一些特殊情况，造成排序的失败。

比如说我们先将最大的值赋给尾部元素，如果最大的值正好在头部元素，而最小的值恰好在尾部元素，这样就导致把最大的元素赋给尾部元素时，会把尾部本来的最小值覆盖掉，造成排序的失败。

为了解决这种情况，我们只需要将尾部元素提前存储好就欧克拉~

原码：

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--;}
}

时间复杂度：
n + n-2 + n - 4 + n - 6……

这也是一个等差数列，所以时间复杂度就是O(N^2)。

显然这并不是一个优的排序算法。