選擇排序

基本思想：

? ? 每一次從待排序的數據元素中選出最小（或最大）的一個元素，存放在序列的起始位置，直到全部待排序的數據元素排完 。

直接選擇排序

? ? 在元素集合array[i]–array[n-1]中選擇關鍵碼最大(小)的數據元素
? ? 若它不是這組元素中的最后一個(第一個)元素，則將它與這組元素中的最后一個（第一個）元素交換在剩余的array[i]–array[n-2]（array[i+1]–array[n-1]）集合中，重復上述步驟，直到集合剩余1個元素

void SelectSort(int* a, int n)
{
? ? int begin = 0, end = n - 1;//記錄末尾和開始位置

? ? while (begin < end)//當begin小于end說明數組沒有被完全排序
? ? {
? ? ? ? // [begin, end]
? ? ? ? int mini = begin, maxi = begin;//將開始位置的值的下標賦予mini，maxi
? ? ? ? for (int i = begin + 1; i <= end; i++)
? ? ? ? {
? ? ? ? ? ? if (a[i] > a[maxi])//比開始位置值大則maxi記錄這一位置的下標
? ? ? ? ? ? {
? ? ? ? ? ? ? ? maxi = i;
? ? ? ? ? ? }

? ? ? ? ? ? if (a[i] < a[mini])//比開始位置值小則mini記錄這一位置的下標
? ? ? ? ? ? {
? ? ? ? ? ? ? ? mini = i;
? ? ? ? ? ? }
? ? ? ? }

? ? ? ? Swap(&a[begin], &a[mini]);//最小值與開始值交換
? ? ? ? // max如果被換走了，修正一下
? ? ? ? if (maxi == begin)
? ? ? ? {
? ? ? ? ? ? maxi = mini;
? ? ? ? }

? ? ? ? Swap(&a[end], &a[maxi]);
? ? ? ? ++begin;
? ? ? ? --end;
? ? }
}

直接選擇排序的特性總結：

? ? 直接選擇排序思考非常好理解，但是效率不是很好。實際中很少使用
? ? 時間復雜度：O(N^2)
? ? 空間復雜度：O(1)
? ? 穩定性：不穩定