排序算法之选择排序
1.选择排序介绍
选择排序分为三种，直接选择排序、树形选择排序、堆排序。直接选择排序和堆排序是不稳定排序，树形选择排序是稳定排序。在这里介绍的是直接选择排序。其他的后面再分析。
直接选择排序算法思想：第一趟从n个元素的数据序列中选出关键字最小/大的元素并放在最前/后位置，下一趟从n-1个元素中选出最小/大的元素并放在最前/后位置。以此类推，经过n-1趟完成排序。
2.选择排序算法分析
直接选择排序的最好时间复杂度和最差时间复杂度都是O(n²)，因为即使数组一开始就是正序的，也需要将两重循环进行完，平均时间复杂度也是O(n²)。空间复杂度为O(1)，因为不占用多余的空间。直接选择排序是一种原地排序（In-place sort）并且稳定（stable sort）的排序算法，优点是实现简单，占用空间小，缺点是效率低，时间复杂度高，对于大规模的数据耗时长。
算法步骤：
- 第1趟，在待排序记录r[1]~r[n]中选出最小的记录，将它与r[1]交换；
- 第2趟，在待排序记录r[2]~r[n]中选出最小的记录，将它与r[2]交换；
- 以此类推，第i趟在待排序记录r[i]~r[n]中选出最小的记录，将它与r[i]交换，使有序序列不断增长直到全部排序完毕
3.选择排序算法从实现到优化
V1.0
template <typename T>
void SelectionSort2(T a[], int len)
{
for(int i = 0; i < len; i++) {
int MinIndex = i;
for(int j = i+1; j < len; j++) {
if(a[MinIndex] < a[j]) {
MinIndex = j;
}
}
swap(a[MinIndex], a[i]);
}
}
4.选择排序多种场景下的测试
int main() {
int N = 20000;
//稀疏数组，随机性大
int *arr1 = SortTestHelper::CreateRandomArray(N, 0, 1000000);
SortTestHelper::testSort("SelectionSort", SelectSortFunc::SelectionSort2, arr1, N);
//近乎有序
int *arr2 = SortTestHelper::CreateRandomArray(N, 0, 100);
SortTestHelper::testSort("SelectionSort", SelectSortFunc::SelectionSort2, arr2, N);
//基本有序
int *arr3 = SortTestHelper::CreateRandomArray(N, 0, 10);
SortTestHelper::testSort("SelectionSort", SelectSortFunc::SelectionSort2, arr3, N);
delete[] arr1;
delete[] arr2;
delete[] arr3;
return 0;
}
测试结果：
SelectionSort : 0.424071s SelectionSort : 0.416928s SelectionSort : 0.410701s
根据结果表明，选择排序是一种稳定的排序算法，在随机性很大和近乎有序，有序的情况下算法的时间复杂度基本不变。但是这也是一个劣势，效率较差。
