选择排序（Selection Sort）

选择排序每一轮从待排序部分挑出最小的元素，和待排序部分的首位交换，已排序的前缀就长出一格。实现只有几行，代价是时间复杂度固定在 $O(n^2)$，数据一多就慢。

1. 选择排序的基本概念

1. 选择最小元素:

   • 从待排序的列表中选择最小的元素。
   • 将这个最小的元素与当前待排序范围的第一个元素交换位置。

2. 缩小排序范围:

   • 将已排序的元素部分扩展到列表的开始位置，将未排序的元素范围缩小。
   • 重复上述步骤，直到所有元素排序完成。

2. 选择排序的算法步骤

1. 外层循环: 从列表的起始位置到倒数第二个元素。

   • 在未排序部分选择最小的元素。

2. 内层循环: 从当前起始位置到列表的末尾，找到最小元素的索引。

3. 交换位置:

   • 将找到的最小元素与当前起始位置的元素交换。

4. 重复:

   • 继续对剩下的未排序部分重复上述步骤，直到整个列表排序完成。

3. 选择排序的时间复杂度和空间复杂度

• 时间复杂度:

  • 最坏情况: $O(n^2)$，无论数据的初始状态如何，每次选择最小元素都需要遍历未排序的部分。
  • 最佳情况: $O(n^2)$，即使数组已经排序好，仍需进行完整的遍历。
  • 平均情况: $O(n^2)$，对随机排序的数组进行排序时，平均时间复杂度为 $O(n^2)$。

• 空间复杂度:

  • 空间复杂度: $O(1)$，选择排序是就地排序算法，不需要额外的存储空间，除了用于交换的变量。

4. 选择排序的代码示例

package main

import "fmt"

// SelectionSort 对整数切片进行选择排序
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, 34, 25, 12, 22, 11, 90}
    fmt.Println("Original array:", arr)
    SelectionSort(arr)
    fmt.Println("Sorted array:", arr)
}

5. 选择排序的优缺点

优点:

• 实现简单，易于理解和编写。
• 对于小规模数据集表现良好。

缺点:

• 时间复杂度为 $O(n^2)$，对大规模数据集效率较低。
• 不稳定排序算法（相同值的元素可能会改变相对位置）。

总结

选择排序有三个确定的性质：时间复杂度固定 $O(n^2)$，与初始排列无关；空间 $O(1)$，只用到交换的变量；实现短，读代码时一眼能看懂排序是怎么进行的。大规模数据不适合用它；短小的实现倒适合拿来对照排序过程。

参考资料

• 选择排序 · Wikipedia

同层页面

• BubbleSort
• BucketSort
• CocktailSort
• RadixSort
• ShellSort

相关页面

• RadixSort
• ShellSort