Selection Sort - HolmesJJ/Data-Structures-and-Algorithms GitHub Wiki

入门链接

6分钟搞定选择排序法 新手向的编程学习：选择排序法 演算法 -- 六種排序法之一：選擇排序法（selection sort）

图解

详解

详解选择排序算法 为什么说选择排序不稳定

标准写法

步骤1: 记录最小值元素的索引和值

public static void selectSort(int[] arr) {

    int minIndex; // 最小值元素索引
    int minNum; // 最小值元素值
}

步骤2: 两层循环

• 外层循环：需要比较的轮数，把N个数进行N-1轮排序
• 内层循环：在当前轮中，遍历每一个元素并比较

public static void selectSort(int[] arr) {

    int minIndex; // 最小值元素索引
    int minNum; // 最小值元素值
    for (int i = 0; i < arr.length - 1; i++) {
        // 记录当前第一个元素为最小值元素
        minIndex = i;
        minNum = arr[i];
        for (int j = 1; j < arr.length; j++) {

        }
    }
}

步骤3: 元素交换

public static void selectSort(int[] arr) {

    int minIndex; // 最小值元素索引
    int minNum; // 最小值元素值
    for (int i = 0; i < arr.length - 1; i++) {
        // 记录当前第一个元素为最小值元素
        minIndex = i;
        minNum = arr[i];
        for (int j = 1; j < arr.length; j++) {
            if (minNum > arr[j]) {
                minNum = arr[j];
                minIndex = j;
            }
        }
        // 交换，这里的交换不需要设置temp，minNum就是一个temp
        if (minIndex != i) {
            arr[minIndex] = arr[i];
            arr[i] = minNum;
        }
    }
}

步骤3: 优化

public static void selectSort(int[] arr) {

    int minIndex; // 最小值元素索引
    int minNum; // 最小值元素值
    for (int i = 0; i < arr.length - 1; i++) {
        // 记录当前第一个元素为最小值元素
        minIndex = i;
        minNum = arr[i];
        // 每一轮都能够确认一个元素的位置
        // 因此，每进行一轮，内层循环都能减少一次遍历
        for (int j = i + 1; j < arr.length; j++) {
            if (minNum > arr[j]) {
                minNum = arr[j];
                minIndex = j;
            }
        }
        // 交换，这里的交换不需要设置temp，minNum就是一个temp
        if (minIndex != i) {
            arr[minIndex] = arr[i];
            arr[i] = minNum;
        }
    }
}

要点

• 把N个数进行N-1轮排序，注意是"轮"
• 既可以升序排序，也可以降序排序，把if中的获得当前最小（大）值的条件 a[j] < minNum 改为 a[j] > maxNum 即可
• 最好时间复杂度是O(n^2)；平均时间复杂度是O(n^2)；最坏时间复杂度是O(n^2)
• 空间复杂度O(1)