選擇排序（基本排序算法）—— 不穩(wěn)定?。?！
動(dòng)態(tài)圖：
一、概念：
原理：就是從需要排序（待排序 ）的數(shù)據(jù)中選擇最小的（從小到大排序），然后放在第一個(gè)，選擇第二小的放在第二個(gè)……
二、基本操作（步驟）：
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)) //求排序時(shí)間，與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)
}
三、時(shí)間、空間復(fù)雜度與排序穩(wěn)定性：
??不難看出，尋找最小的元素需要一個(gè)循環(huán)的過程，而排序又是需要一個(gè)循環(huán)的過程。因此顯而易見，這個(gè)算法的時(shí)間復(fù)雜度是O(n*n)的。這就意味值在n比較小的情況下，算法可以保證一定的速度，當(dāng)n足夠大時(shí)，算法的效率會降低。并且隨著n的增大，算法的時(shí)間增長很快。因此使用時(shí)需要特別注意。
時(shí)間復(fù)雜度： O(n^2)
??選擇排序的復(fù)雜度分析。第一次內(nèi)循環(huán)比較N - 1次，然后是N-2次，N-3次，……，最后一次內(nèi)循環(huán)比較1次。共比較的次數(shù)是 (N - 1) + (N - 2) + … + 1，求等差數(shù)列和，得(N?1+1)?N/2=(N^2) /2(N - 1 + 1)* N / 2 = (N^2) / 2(N?1+1)?N/2=(N^2)/2。舍去最高項(xiàng)系數(shù)，其時(shí)間復(fù)雜度為 O(N^2)。
??雖然選擇排序和冒泡排序的時(shí)間復(fù)雜度一樣，但實(shí)際上，選擇排序進(jìn)行的交換操作很少，最多會發(fā)生 N - 1次交換。而冒泡排序最壞的情況下要發(fā)生N^2 /2交換操作。從這個(gè)意義上講，交換排序的性能略優(yōu)于冒泡排序。而且，交換排序比冒泡排序的思想更加直觀。
空間復(fù)雜度：O(1)
??最優(yōu)的情況下（已經(jīng)有順序）復(fù)雜度為：O(0) ；最差的情況下（全部元素都要重新排序）復(fù)雜度為：O(n )；平均的復(fù)雜度：O(1)
穩(wěn)定性：不穩(wěn)定
??理由 ==> 在一趟循環(huán)排序中，如果當(dāng)前元素比一個(gè)元素小，而該小的元素又出現(xiàn)在和當(dāng)前元素相等 的元素的后面，那么交換后穩(wěn)定性就被破壞了。
??例子 ==> 序列5 8 5 2 9，我們知道第一遍選擇第1個(gè)元素5會和2交換，那么原序列中2個(gè)5的相對前后順序就被破壞了，所以選擇排序不是一個(gè)穩(wěn)定的排序算法。
