数组排序简介-选择排序（Selection Sort）

基本思想

将数组分为两个区间：左侧为已排序区间，右侧为未排序区间。每趟从未排序区间中选择一个值最小的元素，放到已排序区间的末尾，从而将该元素划分到已排序区间。

算法步骤

假设数组的元素个数为 n个，则选择排序的算法步骤如下

初始状态下，无已排序区间，未排序区间为 [0,n−1]

第 1趟选择：

遍历未排序区间 [0,n−1]，使用变量 min_i 记录区间中值最小的元素位置。
将 min_i 与下标为 0 处的元素交换位置。如果下标为 0 处元素就是值最小的元素位置，则不用交换。
此时，[0,0]为已排序区间，[1,n−1]（总共 n−1个元素）为未排序区间。

第 22 趟选择：
1. 遍历未排序区间 [1,n−1]，使用变量 min_i 记录区间中值最小的元素位置。
2. 将 min_i 与下标为 1 处的元素交换位置。如果下标为 1 处元素就是值最小的元素位置，则不用交换。
3. 此时，[0,1]为已排序区间，[2,n−1]（总共 n−2个元素）为未排序区间。
依次类推，对剩余未排序区间重复上述选择过程，直到所有元素都划分到已排序区间，排序结束。

我们以 [5,2,3,6,1,4]为例，演示一下选择排序的整个步骤。

适用情况

选择排序方法在排序过程中需要移动较多次数的元素，并且排序时间效率比较低。因此，选择排序方法比较适合于参加排序序列的数据量较小的情况。选择排序的主要优点是仅需要原地操作无需占用其他空间就可以完成排序，因此在空间复杂度要求较高时，可以考虑选择排序。

排序稳定性

由于值最小元素与未排序区间第 11 个元素的交换动作是在不相邻的元素之间进行的，因此很有可能会改变相等元素的相对顺序，因此，选择排序法是一种 不稳定排序算法。

代码实现(golang)

func selectionSort(arr []int) {
    n := len(arr)
    for i := 0; i < n-1; i++ {
       minIndex := i
       for j := i + 1; j < n; j++ {
          if arr[j] < arr[minIndex] {
             minIndex = j
          }
       }
       if minIndex!= i {
          arr[i], arr[minIndex] = arr[minIndex], arr[i]
       }
    }
}

func main() {
    arr := []int{64, 25, 12, 22, 11, 90}
    selectionSort(arr)
    fmt.Println(arr) // 输出 [11 12 22 25 64 90]
}

选择排序与冒泡排序比较

时间复杂度

两种算法的平均时间复杂度和最坏时间复杂度都是O(n^2)，

然而，在最好情况下，冒泡排序如果数组一开始就是有序的，那么只需要进行一轮遍历就可以确定数组已经有序，时间复杂度为O(n)

而选择排序无论数组初始状态如何，都需要进行相同数量的比较和交换操作，所以最好情况下时间复杂度仍然是 O(n^2)。

空间复杂度

冒泡排序和选择排序都是原地排序算法，即它们只需要常数级别的额外空间，空间复杂度为O(1)。

稳定性

冒泡排序是稳定的排序算法

选择排序是不稳定的排序算法

适用场景

数据规模较小：
当数据规模较小时，冒泡排序和选择排序都可以使用。
稳定性要求：
如果需要保持相等元素的相对顺序，即对稳定性有要求，那么应该选择冒泡排序。
对性能要求不高：
如果对排序算法的性能要求不是特别高，并且更注重代码的简洁性和易理解性，冒泡排序和选择排序是不错的选择。

秒客网