软考-软件设计师：排序算法-直接选择排序

作者：马育民 • • 阅读：10085

介绍

直接选择排序，也称为 选择排序，步骤：

  1. 从所有元素中，找到最小的元素，与第1个元素交换位置
  2. 在剩下的元素中，找到最小的元素，与第2个元素交换位置
  3. …以此类推，直到排序结束

提示：

  • 排序过程中，数组被划分为两个区域：已排序区（左） 和待排序区（右）；

  • 每一轮只做 1次交换（找到最值后才交换），这是它和冒泡排序的核心区别（冒泡每轮可能多次交换）。

例-详细过程

以数组 [2, 5, 8, 3, 6, 9, 1, 4, 7] 为例，长度是 9

第 1 轮

已排序序列是空
未排序序列：2,5,8,3,6,9,1,4,7

执行内层循环，索引 从 1 到 8 逐一遍历，与 未排序序列 的 第一个元素 2比较：

  • 索引是 1（值 5）：5>2，此时最小值是 2
  • 索引是 2（值 8）：8>2，最小值不变
  • 索引是 3（值 3）：3>2，最小值不变
  • 索引是 4（值 6）：6>2，最小值不变
  • 索引是 5（值 9）：9>2，最小值不变
  • 索引是 6（值 1）：1<2，此时最小值是 1
  • 索引是 7（值 4）：4>1，最小值不变
  • 索引是 8（值 7）：7>1，最小值不变

交换操作：交换 未排序序列 的 第一个元素 2，与 最小值1 的位置

本轮结果：[1,5,8,3,6,9,2,4,7]

  • 已排序序列1
  • 未排序序列 5,8,3,6,9,2,4,7

第 2 轮

已排序序列：1
未排序序列：5,8,3,6,9,2,4,7

执行内层循环，索引 从 2 到 8 逐一遍历，与 未排序序列 的 第一个元素 5比较：

  • 索引是 2（值 8）：8>5，此时最小值是 5
  • 索引是 3（值 3）：3<5，此时最小值是 3
  • 索引是 4（值 6）：6>3，最小值不变
  • 索引是 5（值 9）：9>3，最小值不变
  • 索引是 6（值 2）：2<3，此时最小值是 2
  • 索引是 7（值 4）：4>2，最小值不变
  • 索引是 8（值 7）：7>2，最小值不变

交换操作：交换 未排序序列 的 第一个元素 5，与 最小值2 的位置

本轮结果：[1,2,8,3,6,9,5,4,7]

  • 已排序序列1,2
  • 未排序序列 8,3,6,9,5,4,7

第 3 轮

已排序序列：1,2
未排序序列：8,3,6,9,5,4,7

执行内层循环，索引 从 3 到 8 逐一遍历，与 未排序序列 的 第一个元素 8比较：

  • 索引是 3（值 3）：3<8，此时最小值是 3
  • 索引是 4（值 6）：6>3，最小值不变
  • 索引是 5（值 9）：9>3，最小值不变
  • 索引是 6（值 5）：5>3，最小值不变
  • 索引是 7（值 4）：4>3，最小值不变
  • 索引是 8（值 7）：7>3，最小值不变

交换操作：交换 未排序序列 的 第一个元素 8，与 最小值3 的位置

本轮结果：[1,2,3,8,6,9,5,4,7]

  • 已排序序列1,2,3
  • 未排序序列 8,6,9,5,4,7

第 4 轮

已排序序列：1,2,3
未排序序列：8,6,9,5,4,7

执行内层循环，索引 从 4 到 8 逐一遍历，与 未排序序列 的 第一个元素 8比较：

  • 索引是 4（值 6）：6<8，此时最小值是 6
  • 索引是 5（值 9）：9>6，最小值不变
  • 索引是 6（值 5）：5<6，此时最小值是 5
  • 索引是 7（值 4）：4<5，此时最小值是 4
  • 索引是 8（值 7）：7>4，最小值不变

交换操作：交换 未排序序列 的 第一个元素 8，与 最小值4 的位置

本轮结果：[1,2,3,4,6,9,5,8,7]

  • 已排序序列1,2,3,4
  • 未排序序列 6,9,5,8,7

第 5 轮

过程同上

本轮结果：[1,2,3,4,5,9,6,8,7]

  • 已排序区间1,2,3,4,5
  • 未排序区间9,6,8,7

第 6 轮

过程同上

本轮结果：[1,2,3,4,5,6,9,8,7]

  • 已排序区间1,2,3,4,5,6
  • 未排序区间9,8,7

第 7 轮

过程同上

本轮结果：[1,2,3,4,5,6,7,8,9]

  • 已排序区间1,2,3,4,5,6,7
  • 未排序区间8,9

第 8 轮

已排序序列：1,2,3,4,5,6,7
未排序序列：8,9

执行内层循环，索引 从 8 到 8 逐一遍历，与 未排序序列 的 第一个元素 8比较：

  • 索引是 8（值 9）：9>8，最小值是 8

交换操作：最小值就是未排序起始元素，无需交换；

本轮结果：[1,2,3,4,5,6,7,8,9]

  • 已排序区间1,2,3,4,5,6,7,8
  • 未排序区间9（只剩一个元素，不需要执行第 9 轮）

最终结果

原数组 [2,5,8,3,6,9,1,4,7] 经过 8 轮选择排序后，得到升序有序数组：
[1, 2, 3, 4, 5, 6, 7, 8, 9]

例子-简单过程

将 T=(21,25,49,27,16,08) 进行排序

第1轮

取出第一个元素 21，与其他 5 个元素进行比较

找到最小值 08，与第 1 个元素交换位置，结果：
【08】,25,49,27,16,21

第2轮

在 剩下的元素 中，即：25,49,27,16,21，取出第一个元素 25，与其他 4 个元素进行比较

找到最小值 16，与第 2 个元素交换位置，结果：
【08,16】,49,27,25,21

第3轮

在 剩下的元素 中，即：49,27,25,21，取出第一个元素 49，与其他 3 个元素进行比较

找到最小值 21，与第 3 个元素交换位置，结果：
【08,16,21】,27,25,49

第4轮

在 剩下的元素 中，即：27,25,49，取出第一个元素 27，与其他 2 个元素进行比较

找到最小值 25，与第 4 个元素交换位置，结果：
【08,16,21,25】,27,49

第5轮（即：n-1轮）

在 剩下的元素 中，即：27,49，取出第一个元素 27，与另 1 个元素进行比较

找到最小值 27，位置不动，结果：
【08,16,21,25,27】,49

时间复杂度

O(n^2)

最好、最坏、平均 都是 O(n²)，因为每次都会比较

计算过程

有上面例子可知：

第1轮：循环 n - 1 次
第2轮：循环 n - 2 次
...
第n-1轮：循环 1 次

所以计算公式：

(n-1) + (n-2) + ... + 2 + 1 = n(n-2)/2

大O表示法：O(n^2)

空间复杂度

O(1)

是否稳定排序

不稳定

例子

数组 [2, 2*, 1]，第一轮找到最小值1，和第一个2交换，结果为 [1, 2*, 2]，原 2 和 2* 的 相对位置颠倒。

优缺点

优点

  1. 逻辑简单，代码易写易理解，入门排序的最佳选择之一；
  2. 交换次数极少，在 数据交换成本远高于比较成本 的场景（如磁盘数据排序），比冒泡排序更优；
  3. 原地排序，空间复杂度低，无需额外内存。

缺点

  1. 时间复杂度固定 O(n²)，大数据量下 效率极低；
  2. 不稳定排序，对有稳定性要求的场景（如学生成绩排序：分数相同保留原顺序）不适用；
  3. 无优化空间，无法通过提前终止循环提升效率。

实现

代码极简，两层循环即可实现，原地排序（无需额外开辟数组空间）

java版

public class SelectionSort {
    // 升序选择排序核心方法：传入int数组，原地排序
    public static void selectionSortAsc(int[] arr) {
        // 空数组或单元素数组，直接返回（无需排序）
        if (arr == null || arr.length <= 1) {
            return;
        }
        int n = arr.length;
        // 外层循环：控制待排序区起始位置，共n-1轮（最后1个元素天然有序）
        for (int i = 0; i < n - 1; i++) {
            int minIndex = i; // 假设当前待排序区第一个元素是最小值，记录其索引
            // 内层循环：遍历待排序区（i+1到n-1），找到真正的最小值索引
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j; // 更新最小值索引（仅记录，不交换）
                }
            }
            // 找到最小值后，交换待排序区第一个元素和最小值元素（每轮最多1次交换）
            swap(arr, i, minIndex);
        }
    }

    // 工具方法：交换数组中两个索引的元素（抽离出来，提高代码复用性）
    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    // 测试方法：打印数组（直观查看排序结果）
    public static void printArray(int[] arr) {
        if (arr == null) {
            System.out.println("数组为空");
            return;
        }
        for (int num : arr) {
            System.out.print(num + " ");
        }
        System.out.println();
    }

    // 主方法：测试升序排序
    public static void main(String[] args) {
        int[] testArr = {5, 2, 9, 1, 5, 6};
        System.out.println("排序前：");
        printArray(testArr); // 输出：5 2 9 1 5 6
        selectionSortAsc(testArr);
        System.out.println("升序排序后：");
        printArray(testArr); // 输出：1 2 5 5 6 9
    }
}

python版

def selection_sort(arr):
    # 获取数组长度，n个元素只需排序n-1轮（最后1个元素天然有序）
    n = len(arr)
    # 外层循环：控制待排序区的起始位置，共n-1轮
    for i in range(n - 1):
        # 假设当前待排序区第一个元素是最小值，记录其索引（关键：存索引而非值）
        min_index = i
        # 内层循环：遍历待排序区（i+1到n-1），找到真正的最小值索引
        for j in range(i + 1, n):
            if arr[j] < arr[min_index]:
                min_index = j  # 更新最小值索引
        # 找到最小值后，交换待排序区第一个元素和最小值元素
        arr[i], arr[min_index] = arr[min_index], arr[i]
    return arr

# 测试代码
if __name__ == "__main__":
    test_arr = [5, 2, 9, 1, 5, 6]
    selection_sort(test_arr)
    print("排序后数组：", test_arr)  # 输出：[1, 2, 5, 5, 6, 9]

总结

  1. 选择排序属于 减治思想，核心是 每轮找最值+一次交换，将数组划分为已排序/待排序区；
  2. 代码极简，原地排序（O(1) 空间），但时间复杂度固定O(n²)，仅适用于小规模数据；
  3. 不稳定排序，交换次数远少于冒泡排序，是更实用的$O(n^2)$级排序；
  4. 升序/降序仅需修改判断条件，易扩展。

原文出处：/show_1GWwqJ9GRAF.html

吉ICP备15003043号