选择排序（附动图）

1.思路

基本思想：
每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。

1.1双向选择排序（升序）

头尾指针（索引），每一次从待排序的数据元素中选出最小的一个元素，存放在序列头，最大的元素存放在序列尾，直到头指针（索引）大于等于尾指针（索引），序列排序完毕。

2.动图

3.代码

3.1单向

#include<iostream>
using namespace std;void Swap(int* px, int* py) {int tmp = *px;*px = *py;*py = tmp;
}void SelectSort(int* a, int n) {for (int i = 0; i < n - 1; i++) {int minIndex = i;for (int j = i + 1; j < n; j++) {if (a[j] < a[minIndex]) {minIndex = j;}}Swap(&a[minIndex], &a[i]);}
}int main() {int a[] = { 5, 3, 2, 1, 6, 7, 8, 0 };int n = sizeof(a) / sizeof(a[0]);SelectSort(a, n);for (int i = 0; i < n; i++) {cout << a[i] << " ";}cout << endl;return 0;
}

3.2双向

#include<iostream>
using namespace std;
void Swap(int* px, int* py)
{int tmp = *px;*px = *py;*py = tmp;
}
void SelectSort(int* a, int n)
{int begin = 0;int end = n - 1;while (begin < end){int mini = begin, maxi = end;for (int i = begin + 1; i <= end; i++){if (a[i] < a[mini]){mini = i;}if (a[i] > a[maxi]){maxi = i;}}Swap(&a[mini], &a[begin]);if (maxi == begin){maxi = mini;}Swap(&a[maxi], &a[end]);++begin;--end;}
}
int main()
{int a[] = { 5,3,2,1,6,7,8,0 };SelectSort(a, sizeof(a) / sizeof(int));for (int i = 0; i < sizeof(a) / sizeof(int); i++){cout << a[i] << " ";}cout << endl;
}