【排序】选择排序，不稳定｜Java 刷题打卡

一、前言

选择排序：是一种简单直观的排序算法

这个算法把数组分为 有序区 和 无序区，每次都选择无序区中的最大值或最小值，放入有序区中，直到整个数组都有序。

同样，选择排序，每次遍历均会确定一个有序位置。

举栗，动图如下：

二、知识点

知识点，如下：

1. 时间复杂度
2. 逆序对
3. 实现：简单实现

PS: 实习生的面试，会遇到

（1）时间复杂度

• 最坏情况：逆序，时间复杂度 O(N ^ 2)

• 稳定性：不稳定。

  例如，原数组 {4, 1, 4}

  不稳定：排序过程中，第二个 4 排在了 第一个 4 前面。

排序总图，如图：

（2）逆序对

逆序对（inversion）：对于下标 i < j，如果 arr[i] > a[j]，则称 (i, j) 是一对逆序对。

举个栗子，序列 {34, 8, 64, 51, 32, 21} 有多少逆序对？

有9对：

(34, 8), (34, 32), (34, 21), (64, 51), 

(64, 32), (64, 21), (51, 32), (51, 21), (32, 21)
复制代码

可得定理：

• 定理：任意 N 个不同元素组成的序列平均具有 N(N-1)/4 个逆序对
• 定理：任何仅以交换相邻两元素来排序的算法，其平均时间复杂度为 O(N^2)

那么逆序对，有什么用呢？

1. 代表了，需要交换的次数。

2. 为提高算法效率提供基础

那么要提高算法效率，必须：

1. 每次消去不止 1个逆序对

2. 每次交换相隔较远的 2个元素

（3）实现

从前往后排序，代码如下：

public class SelectSort {

    // Time: O(n^2), Space: O(1)
    public void sort(int[] arr) {
        if (arr == null || arr.length == 0) return;
        int n = arr.length;
        for (int i = 0; i < n; ++i) {
            int minIdx = i;
            for (int j = i+1; j < n; ++j)
                if (arr[j] < arr[minIdx])
                    minIdx = j;
            swap(arr, i, minIdx);
        }
    }

    private void swap(int[] arr, int i, int j) {
        if (i == j) return;
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}
复制代码