《选择排序算法》

发表于 分类于 ， 阅读次数： 本文字数： 632 阅读时长 ≈ 2 分钟
个人公众号

《算法与数据结构：选择排序算法》

选择排序算法

简介

选择排序是一种简单直观的排序算法。它的工作原理是每次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。选择排序是不稳定的排序方法（即相同的元素可能在排序后的序列中有不同的顺序）。

算法原理

选择排序算法的主要步骤如下：

  1. 在未排序序列中找到最小（或最大）元素，存放到排序序列的起始位置。
  2. 从剩余未排序元素中继续寻找最小（或最大）元素，然后放到已排序序列的末尾。
  3. 重复第二步，直到所有元素均排序完毕。

算法演示

假设有一个未排序的数组：[5, 3, 6, 2, 10]

步骤当前数组状态选中元素
15, 3, 6, 2, 102
22, 3, 6, 5, 103
32, 3, 6, 5, 105
42, 3, 5, 6, 106
52, 3, 5, 6, 1010

图画演示

创建一个演示数组【3，5，1，2，4】，数组长度为 5，数组表示为 nums [0,5) 左闭右开区间。

图1 选择最小元素1 与未排序队列的第一个元素交换

图2 从剩余未排序队列中寻找最小值与未排序队列中第一元素交换

img

img

动画 GIF 演示

选择排序算法GIF动画

Java 代码实现

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
public class SelectionSort {
    
    /**
     * 宏观前提  数组左闭右开
     * i 表示进行的第i轮排序
     * nums[0,i)已经排序
     * nums[i,n)未排序
     * 每轮排序从未排序的列表中选择最小的元素，放在未排序的列表起始位置i上
     *
     * @param nums 待排序数组
     */
    public static void selectionSort(int[] nums) {
        int len = nums.length;

        for (int i = 0; i < len; i++) {
            // 记录未排序列表中最小元素下标
            int minIndex = i;
            for (int j = i; j < len; j++) {
                if (nums[minIndex] > nums[j]) {
                    minIndex = j;
                }
            }
            swap(nums, i, minIndex);
        }
    }
    private static void swap(int[] nums, int low, int high) {
        int temp = nums[low];
        nums[low] = nums[high];
        nums[high] = temp;
    }
}

Java 范型实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class SelectionSort {
    
    public static <E extends Comparable<? super E>> void selectionSort(E[] nums) {
        int len = nums.length;

        for (int i = 0; i < len; i++) {
            int minIndex = i;
            for (int j = i; j < len; j++) {
                if (nums[minIndex].compareTo(nums[j]) > 0) {
                    minIndex = j;
                }
            }
            swap(nums, minIndex, i);
        }
    }
    private static <E extends Comparable<? super E>> void swap(E[] nums, int low, int high) {
        E temp = nums[low];
        nums[low] = nums[high];
        nums[high] = temp;
        // help gc
        temp = null;
    }
}

github 项目