【基础算法】排序算法 —— 选择排序

一、算法原理

选择排序将数组分为已排序区间和未排序区间，每次选择未排序区间的最小元素，将它放到已排序区间末尾。一次选择会让一个元素移动到它应该在的位置，重复 n 次，就完成了 n 个数据的排序。

示例：使用选择排序对数组 arr = [4，5，6，3，2，1] 从小到大排序。

第1次选择：

第2次选择：

第3次选择：

第4次选择：

第5次选择：

第6次选择：

二、选择排序优化

思路：选择未排序区间的最小元素，不需要出现小于当前元素的就交换，可以只记住下标，本次选择完成之后再交换，这样每一次选择只需要交换一次，省去了很多次无效交换。

三、代码实现

/**
 * 选择排序，时间复杂度 O(n^2)，空间复杂度 O(1)，不稳定
 *
 * @param arr 待排序数组
 */
public static void selectSort(int[] arr) {
    if (arr == null || arr.length < 2) {
        return;
    }

    for (int i = 0, len = arr.length; i < len - 1; i++) { // 未排序区间的下标
        int min = i; // 选择未排序区间第1个元素为最小元素
        for (int j = i + 1; j < len; j++) { // 一次与之后的元素比较
            if (arr[j] < arr[min]) {
                min = j;
            }
        }
        if (min != i) { // 将最小元素交换至已排序区间末尾
            swap(arr, min, i);
        }
    }
}

private static void swap(int[] arr, int i, int j) {
    if (i == j) {
        return;
    }
    arr[i] = arr[i] ^ arr[j];
    arr[j] = arr[i] ^ arr[j];
    arr[i] = arr[i] ^ arr[j];
}

四、算法评价

4.1 时间复杂度

选择排序的最好、最坏、平均时间复杂度都是 O(n²)，因为不论数组原来是否有序，每次都要从未排序区间找到最小值，而最小值只能通过全部比较一次才能得到。

4.2 空间复杂度

选择排序只需要常量级的临时空间，所以它的空间复杂度为 O(1)，是一个原地排序算法。

4.3 稳定性

选择排序是一种不稳定的排序算法，因为每次都要从未排序区间找最小值，并和前面的元素交换位置，破坏了稳定性。比如，数组 [5，6，5，2，3]，第一次找到的最小元素是 2，与第1个 5 交换位置，这样第1个 5 和第2个 5 的顺序已经改变了。