选择排序

package main

import "fmt"

func main() {
    arr := []int{7, 13, 4, 5, 8, 1, 11, 9}

    fmt.Println("排序前：", arr)

    length := len(arr)

    for i := 0; i < length; i++ {
        for j := i+1; j < length; j++ {
            if arr[i] > arr[j] {
                arr[i], arr[j] = arr[j], arr[i]
            }
        }
    }

    fmt.Println("排序前：",arr)
}

选择排序的时间复杂度

首先，为了在第 1 轮找到最小的数字，需要从左往右确认数列中的数字，只要查询 n 个数
字即可。在接下来的第 2 轮中，需要从 n -1 个数字中寻找最小值，所以需要查询 n -1 个数字。
将这个步骤进行到第 n 轮的时候，需要查询的次数如下。

n+( n- 1)+(n-2)+…3+2 +1=n(n+1)/2≤ n^2

其中 O 这个符号的意思是“忽略重要项以外的内容”，读音同 Order。 O(n^2) 的含义就是“算法的运行时间最长也就是 n^2 的常数倍”，准确的定义请参考相关专业书籍。重点在于，通过这种表示方法，我们可以直观地了解算法的时间复杂度 A。

故我们知道选择排序的时间复杂度为 O(n^2)。

有疑问加站长微信联系（非本文作者）