选择排序法

同样基于交换的思想，选择排序法的效率要比冒泡排序高很多。

核心思想

将数据分成两组，通过遍历找到极值，并存放到另一组末尾。

选择排序

选择查找极值

选择法查找极值

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

private static int max(int[] original) {
    int[] arr = Arrays.copyOf(original, original.length);

    int i = 0;
    int pos = i + 1;
    for (; i < arr.length; i++) {
        if (arr[i] > arr[pos]) {
            pos = i;
        }
    }
    return arr[pos];
}

选择法排序

 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

private static int[] sort(int[] original) {
    // copy一份数据出来，不让原数据受影响
    int[] aar = Arrays.copyOf(original, original.length);

    int num;
    // 只遍历n-1次就够了，最后一个数不用管
    for (int i = 0; i < aar.length - 1; i++) {

        // 记录极值的位置
        int minPos = i;

        // 让出已处理过的数据，只需遍历剩下的数据
        for (int j = i + 1; j < aar.length; j++) {
            // 比较并更新位置
            if (aar[j] < aar[minPos]) {
                minPos = j;
            }
        }

        // 一轮遍历之后开始交换
        if (i != minPos) {
            num = aar[i];
            aar[i] = aar[minPos];
            aar[minPos] = num;
        }
    }
    return aar;
}