排序-----选择排序

首先介绍几种排序的分类：

        选择排序是每次都遍历，标记出最小的元素，然后把它放在前面。

        本文介绍优化后的版本：每次遍历标记出最小的和最大的元素，分别放到前面和后面。（注意这里是找到对应的下标，然后将对应下标的数据进行交换）

        注意最后不要忘了begin++和end--。

void SelectSort(int* a, int n)
{int begin = 0, end = n - 1;while (begin < end){int mini = begin, maxi = begin;for (int i = begin + 1; i <= end; ++i){if (a[i] > a[maxi]){maxi = i;}if (a[i] < a[mini]){mini = i;}}Swap(&a[begin], &a[mini]);Swap(&a[end], &a[maxi]);++begin;--end;}
}

但是！这段代码是有问题的！

第一行为原始数据，第二行为排序后的数据：

这显然是不对的！那么问题出现在哪呢？

这个地方第一次交换就出现问题了，因为maxi和begin重叠，导致最大值并没有移动到最后。

所以要加上一个判断条件：

void SelectSort(int* a, int n)
{int begin = 0, end = n - 1;while (begin < end){int mini = begin, maxi = begin;for (int i = begin + 1; i <= end; ++i){if (a[i] > a[maxi]){maxi = i;}if (a[i] < a[mini]){mini = i;}}Swap(&a[begin], &a[mini]);if (begin == maxi)maxi = mini;Swap(&a[end], &a[maxi]);++begin;--end;}
}

这个排序最好情况和最坏情况都是O(N^2)。