选择排序（基本排序算法）—— 不稳定！！！

动态图：

选择排序.gif

一、概念：

原理：就是从需要排序（待排序 ）的数据中选择最小的（从小到大排序），然后放在第一个，选择第二小的放在第二个……

二、基本操作（步骤）：

package main

import (
    "fmt"
    "math/rand"
    "time"
)

//1.
const (
    num      = 100000
    rangeNum = 100000
)

func main() {
    // fmt.Println(time.Now().Unix() , time.Now().UnixNano())
    randSeed := rand.New(rand.NewSource(time.Now().Unix() + time.Now().UnixNano()))
    var buf []int
    for i := 0; i < num; i++ {
        buf = append(buf, randSeed.Intn(rangeNum))
    }
    t := time.Now()
    // 选择排序
    xuanze(buf)
    fmt.Println(time.Since(t))  //求排序时间，与t := time.Now()配合
}
// 选择排序
func xuanze(buf []int) {
    times := 0
    for i := 0; i < len(buf)-1; i++ {
        min := i
        for j := i; j < len(buf); j++ {
            times++
            if buf[min] > buf[j] {
                min = j
            }
        }
        if min != i {
            tmp := buf[i]
            buf[i] = buf[min]
            buf[min] = tmp
        }
    }
    fmt.Println("xuanze times: ", times)
}

三、时间、空间复杂度与排序稳定性：

  不难看出，寻找最小的元素需要一个循环的过程，而排序又是需要一个循环的过程。因此显而易见，这个算法的时间复杂度是O(n*n)的。这就意味值在n比较小的情况下，算法可以保证一定的速度，当n足够大时，算法的效率会降低。并且随着n的增大，算法的时间增长很快。因此使用时需要特别注意。

时间复杂度： O(n^2)
  选择排序的复杂度分析。第一次内循环比较N - 1次，然后是N-2次，N-3次，……，最后一次内循环比较1次。共比较的次数是 (N - 1) + (N - 2) + … + 1，求等差数列和，得(N−1+1)∗N/2=(N^2) /2(N - 1 + 1)* N / 2 = (N^2) / 2(N−1+1)∗N/2=(N^2)/2。舍去最高项系数，其时间复杂度为 O(N^2)。
  虽然选择排序和冒泡排序的时间复杂度一样，但实际上，选择排序进行的交换操作很少，最多会发生 N - 1次交换。而冒泡排序最坏的情况下要发生N^2 /2交换操作。从这个意义上讲，交换排序的性能略优于冒泡排序。而且，交换排序比冒泡排序的思想更加直观。

空间复杂度：O(1)
  最优的情况下（已经有顺序）复杂度为：O(0) ；最差的情况下（全部元素都要重新排序）复杂度为：O(n )；平均的复杂度：O(1)

稳定性：不稳定
  理由 ==> 在一趟循环排序中，如果当前元素比一个元素小，而该小的元素又出现在和当前元素相等 的元素的后面，那么交换后稳定性就被破坏了。
  例子 ==> 序列5 8 5 2 9，我们知道第一遍选择第1个元素5会和2交换，那么原序列中2个5的相对前后顺序就被破坏了，所以选择排序不是一个稳定的排序算法。