​
​

1. 选择排序

• 什么是选择排序？
  就是在待排序列中每次找出最小（大）的元素放到序列首位（已排序序列的末尾）。直至最终排序完毕。

• 工作原理：
  首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

1.1 算法描述

n个记录的直接选择排序可经过n-1趟直接选择排序得到有序结果。具体算法描述如下：

• 初始状态：无序区为R[1…n]，有序区为空；
• 第i趟排序(i=1,2,3…n-1)开始时，当前有序区和无序区分别为R[1…i-1]和R(i…n）。该趟排序从当前无序区中-选出关键字最小的记录 R[k]，将它与无序区的第1个记录R交换，使R[1…i]和R[i+1…n)分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区；
• n-1趟结束，数组有序化了。

1.2 时空复杂度

• 时间复杂度：O(n²) 最好最坏均是。
• 空间复杂度： O(1)
• 稳定性：不稳定（相同元素位置可能发生交换）

1.3 动图演示

1.4 算法实现

public class SelectionSort {
    public static void main(String[] args) {
        int[] arr = {9, 5, 4, 2, 4, 6, 7, 1};

        for (int i = 0; i < arr.length-1; i++) {
            //找出最小位置
            //假定第一个位置为 min position
            int minPos = i;
            for (int j = i+1; j < arr.length; j++) {
                if (arr[j] < arr[minPos]) {
                    minPos = j;
                }
            }
            System.out.println("minPos:"+ minPos);
            //程序执行到此处，说明 minPos 中保存的就是最小位置的下标
            //交换
            swap(arr, i, minPos);
            System.out.println("经过第" + i +"次循环之后：");
            print(arr);
            System.out.println();
        }
        System.out.println("最终排序结果（小-->大）：");
        print(arr);
    }
    
    static void print(int[] arr){
        //遍历数组元素
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }

    //交换
    static void swap(int[] arr, int i, int j) {
        int temp = 0;
        temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}


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
29
30
31
32
33
34
35
36
37
38
39
40
41
42

2. 选择排序优化

同样的思路，我们可以知道上面比较的次数是恒定的，既然每次循环都确定最小值，那为什么不可以顺带确定最大值也固定其位置呢？这样一来，每次循环都找到最大值最小值，循环次数就会减少一半。

来看代码：

/**
 * 选择排序改进
 * 在每一次循环时，找到最小值和最大值，分别放在数组第一个位置和最后一个位置。
 * 循环次数可减少一半
 */
public class SelectionSort {
    public static void main(String[] args) {
        int[] arr = {9, 5, 4, 2, 4, 6, 7, 1};

        for (int i = 0; i < arr.length/2; i++) {
            //找出最小位置
            //假定第一个位置为 min position
            int minPos = i;
            int maxPos = i;
            // j < arr.length-i
            // ”-i“ 防止最大值一直不变
            for (int j = i+1; j < arr.length - i; j++) {
                if (arr[j] < arr[minPos]) {
                    minPos = j;
                }
                if (arr[j] > arr[maxPos]) {
                    maxPos = j;
                }
            }
            System.out.println("minPos:"+ minPos);
            System.out.println("maxPos:"+ maxPos);

            //交换
            swap(arr, i, minPos);
            //因为先确定的是最小值，所以修正 最大值在 i 位置的情况
            //比如说 此时交换完之后，数组变为：【1, 5, 4, 2, 4, 6, 7, 9】
            //交换之后，maxPos由 0 --> 7 即 maxPos = minPos;
            if (maxPos == i) {
                maxPos = minPos;
            }

            swap(arr, arr.length-1-i, maxPos);
            System.out.println("经过第" + i +"次循环之后：");
            print(arr);
            System.out.println();
        }
        System.out.println("最终排序结果（小-->大）：");
        print(arr);
    }

    static void print(int[] arr){
        //遍历数组元素
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }

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


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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

优化后我们可以知道：

减少了交换次数，交换次数为n/2
平均时间复杂度为O(n^2)
依旧不稳定

活动地址：CSDN21天学习挑战赛

---

最不能透支的是健康，最不能浪费的是时间。

​