如需转载请评论或简信，并注明出处，未经允许不得转载

概述

选择排序就是通过遍历找到数组中的最小值，不断的与数组中首个未经过排序的数据进行交换的排序算法

时间复杂度

O(n²)

排序过程

1. 初始化一个数组

   
   

2. 找到数组中最小值

   
   

3. 将最小值与第1个数进行交换

   
   

4. 从第2位数开始找到数组中最小值

   
   

5. 将最小值与第2个数进行交换

   
   

6. 从第3位数开始找到数组中最小值
   ......

不断重复上述步骤，直到数组从小到大排列

代码

public static void sort(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n; i++) {
        // 寻找[i, n)区间里的最小值的索引
        int minIndex = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        //交换 i 和 minIndex
        swap(arr, i, minIndex);
    }
}

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

性能测试

随机生成10,000个从0到10,000的数，分别进行五次测试，效果如下

次数	性能
1	74ms
2	91ms
3	112ms
4	97ms
5	96ms

随机生成100,000个从0到100,000的数，分别进行五次测试，效果如下

次数	性能
1	6635ms
2	5454ms
3	5788ms
4	5322ms
5	6450ms