SortAlgosKt(2) - 选择排序

又是一个颓废的周末，忙着看比赛没怎么学习，罪过罪过。一觉醒来，才知道双11今天凌晨就提前开始了，大家都像打仗一样的奔向战场，而我还在沉浸在香甜的睡梦中（血亏）。不过想想，不买立省100%，也就没那么亏了嘿嘿。不闲扯了，还是来讲讲选择排序吧。

算法思想

runoob 上对选择排序的步骤是这么概括的：

首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。

再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。

重复第二步，直到所有元素均排序完毕。

总结起来就是，每一趟遍历，找出最小的数放在相应的位置

和冒泡排序不同的是，选择排序每趟下来只会在遍历完所有元素后才会进行一次交换，而冒泡排序则是每趟遍历都有可能会进行多次交换，这也是选择排序略优于冒泡排序的地方（这里针对的是未优化前的冒泡排序，优化后的冒泡排序会检测如果某趟遍历没有发生元素交换，就提前结束排序，所以在某些情况下会优于选择排序）。

算法实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

fun selectionSort(nums: IntArray) {
    if (nums.size < 2) return
    //i表示第几趟排序
    for (i in 0 until nums.lastIndex) {
        var minIndex = i//minIndex表示每趟排序最小值的索引
        //j表示这趟排序遍历的索引位置
        for (j in i + 1..nums.lastIndex) {
            if (nums[j] < nums[minIndex]) {
                minIndex = j
            }
        }
        swap(nums, i, minIndex)
    }
}

时间复杂度：O(n^2)

空间复杂度：O(1)