选择排序（Selection Sort）

选择排序是一种直观的排序算法。它的核心思想是不断地从未排序的序列中找到最小（或最大）的元素，然后将其放置在已排序序列的末尾。

选择排序示意图

算法流程

  1. 在未排序序列中找到最小（或最大）元素，存放到排序序列的起始位置。
  2. 再从剩余未排序元素中继续寻找最小（或最大）元素，然后放到已排序序列的末尾。
  3. 重复第二步，直到所有元素均排序完毕。
  • 注意：选择排序是一种不稳定的排序算法。例如：考虑数组 $[2_a, 2_b, 1, 5]$（其中 $2_a$ 和 $2_b$ 的值相等，但 $2_a$ 原本在 $2_b$ 之前）。在第一次迭代中，算法会找到最小元素 1。然后它会将 1 与“第一个”元素 $2_a$ 交换。交换后的数组将变为 $[1, 2_b, 2_a, 5]$。我们可以看到，$2_b$ 现在位于 $2_a$ 之前，打破了它们的相对顺序，因此该排序是不稳定的。

伪代码

算法 5：选择排序伪代码

算法分析

  • 比较次数：外层循环运行 $n-1$ 次（对于长度为 $n$ 的数组，当剩下最后一个元素时，无需再比）。在每一次外层循环中，内层循环会比较未排序部分的所有元素，找到最小的一个。
  • 总比较次数：
    $$\sum_{i=1}^{n-1} \sum_{j=(i+1)}^n 1 = n(n-1)-\sum_{i=1}^{n-1} i=n(n-1)- \frac{n(n-1)}{2}=\frac{n(n-1)}{2}$$
  • 因此，选择排序的时间复杂度在所有情况下均为 $O(n^2)$。
  • 选择排序是一种原地（In-place）排序算法，只需要 $O(1)$ 的额外空间（用于交换元素时的临时变量）。

代码示例

代码示例 11: Java 选择排序实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public static void selectionSort (int array []) {
  int n = array.length;
  // 外层循环：逐步将已排序部分向右扩展
  for (int i = 0; i < n - 1; i++) {
    // 假设当前位置元素为最小
    int index_of_min = i;
    // 内层循环：在未排序部分中寻找实际的最小元素索引
    for (int j = i + 1; j < n; j++) {
      if (array[index_of_min] > array[j]) {
        // 如果找到更小的元素，更新最小元素的索引
        index_of_min = j;
      }
    }
    // 将找到的最小元素与当前位置的元素进行交换
    int temp = array[i];
    array[i] = array[index_of_min];
    array[index_of_min] = temp;
  }
}