选择排序-20240124

发表于 更新于 分类于 阅读次数： 本文字数： 624 阅读时长 ≈ 2 分钟

排序逻辑

「选择排序 selection sort」的工作原理非常简单：开启一个循环，每轮从未排序区间选择最小的元素，将其放到已排序区间的末尾。

设数组的长度为n

  1. 初始状态下，所有元素未排序，即未排序（索引）区间为[0, n-1]。

  2. 选取区间[0, n-1]中的最小元素，将其与索引 0 处的元素交换。完成后，数组前 1 个元素已排序。

  3. 选取区间[1, n-1]中的最小元素，将其与索引 1 处的元素交换。完成后，数组前 2 个元素已排序。

  4. 以此类推。经过 n-1 轮选择与交换后，数组前 n-1 个元素已排序。

  5. 仅剩的一个元素必定是最大元素，无须排序，因此数组排序完成。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
public class SelectionSort {
    /**
     * 设数组的长度为n
     * 1.初始状态下，所有元素未排序，即未排序（索引）区间为[0, n-1]。
     * 2.选取区间[0, n-1]中的最小元素，将其与索引 0 处的元素交换。完成后，数组前 1 个元素已排序。
     * 3.选取区间[1, n-1]中的最小元素，将其与索引 1 处的元素交换。完成后，数组前 2 个元素已排序。
     * 4.以此类推。经过 n-1 轮选择与交换后，数组前 n-1 个元素已排序。
     * 5.仅剩的一个元素必定是最大元素，无须排序，因此数组排序完成。
     *
     * @param nums
     * @author Forest Dong
     * @date 2024/01/25 19:38
     */
    private static void sort(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n - 1; i++) {
            int k = i;
            for (int j = i + 1; j < n; j++) {
                if (nums[j] < nums[k]) {
                    k = j;
                }
            }
            int temp = nums[i];
            nums[i] = nums[k];
            nums[k] = temp;
        }
    }

    public static void main(String[] args) {
        int[] nums = {5, 3, 7, 2, 0, 3, 8};
        sort(nums);
        for (int num : nums) {
            System.err.println(num);
        }
    }
}

算法特性

  • 时间复杂度为 O(n^2)、非自适应排序：外循环共 n−1 轮，第一轮的未排序区间长度为 n ，最后一轮的未排序区间长度为 2 ，即各轮外循环分别包含 n、n−1、…、3、2 轮内循环，求和为 (n−1)(n+2)/2 。
  • 空间复杂度为 O(1)、原地排序：指针 i 和 j 使用常数大小的额外空间。
  • 非稳定排序：如图 11-3 所示，元素 nums[i] 有可能被交换至与其相等的元素的右边，导致两者的相对顺序发生改变。