12、数据结构与算法 - 基础：排序算法之选择排序

1、选择排序基本介绍

选择排序（select sorting）是一种简单的排序方法，它的原理是：从需要排序的数据中，按照指定规则选出某一元素，再按照规定交换位置达到排序的目的。选择排序是不稳定的排序方法

选择排序时间复杂度

选择排序的交换操作介于 0 和 (n - 1) 次之间，比较操作为 n(n - 1) / 2 次之间，赋值操作介于 0 和 3(n - 1) 次之间。比较次数 O(n^2)，比较次数与关键字的初始状态无关。

选择排序与冒泡排序相比，交换次数较少，比冒泡排序更快，最好的情况是有序，交换 0 次，最坏情况交换 n - 1 次，逆序交换 n / 2 次。

2、选择排序思路

1、 选择排序一共有数组大小-1轮排序，每轮排序都是一个循环；
2、 按照循环的规则进行比较，找到对应的数后进行交换；
3、 重复进行上一步操作，直到所有元素均排序完毕；

3、选择排序代码示例

// 排序规则为最小的数，与第一个元素进行交换
public static void selectSort(int[] arr) {
   
     
    int minIndex = 0; // 最小值下标
    int min = arr[0]; // 第一个元素
    for(int i = 0 + 1; i < arr.length; i++) {
   
      // 循环找到最小值
        if(min > arr[i]) {
   
      // 找到最小的值
            min = arr[i];
            minIndex = j;
        }
    }
    // 第一个元素与最小值交换位置
    arr[minIndex] = arr[0];
    arr[0] = min;
}

选择排序代码具体实现

public static void selectSort(int[] arr) {
   
     
    // 外层循环控制遍历次数
    for(int i = 0; i < arr.length - 1; i++ ){
   
     
        int minIndex = i; // 最小值下标
        int min = arr[i]; // 第 i 个位置的元素
        for(int j = i + 1; j < arr.length; j++) {
   
      // 找到后面的最小的元素
            if(min > arr[j]) {
   
     
                min = arr[j];
                minIndex = j;
            }
        }
        // 最小值下标为 i 的话，不用进行交换
        if (minIndex != i) {
   
     
            arr[minIndex] = arr[i];
            arr[i] = min;
        }
    }
}