2.1.2 选择排序

实现原理

找到数组中第一小的元素，和第一元素交换位置。再在剩余的元素中找到第二小的元素和第二个元素交换位置。以此类推，直到整个数组排序。

效率分析

对于每一次排序都需和未排序的元素进行比较一遍。所以需要比较N(N - 1)/2次。每个元素最后都需要进行交换一次。共需交换N次。
时间复杂度为 N

代码实现

func sort(a []int) {
  N := len(a)
  for i := 0; i < N; i++ {
    min := i
    for j := i + 1; j < N; j++ {
      if less(a[j], a[min]) {
        min = j
      }
    }
    exch(a, i, min)
  }
}