数据结构算法之选择排序

选择排序的思路：有n个数据需要从小到大排列，第一轮，固定角标为0的数据，然后遍历其余数据，选出最小的数据与角标为0数据互换，第二轮，固定角标为1数据，然后遍历其余数据，选出最小的数据与角标为1数据互换，依次类推，如图：

图1

写法直接上图：

简单选择排序

选择排序的时间复杂度：简单选择排序的比较次数与序列的初始排序无关。 假设待排序的序列有 N 个元素，则比较次数永远都是N (N - 1) / 2。而移动次数与序列的初始排序有关。当序列正序时，移动次数最少，为 0。当序列反序时，移动次数最多，为3N (N - 1) /  2。

所以，综上，简单排序的时间复杂度为 O(N2)。

适用场景：

选择排序和冒泡排序一样，数据量特别大并且大部分无序的，同样需要大量的两两比较，时间复杂度最好最坏均为O(n2)，所以选择排序适用于数据量非常小的排序。