体育课上课啦

叮铃铃玲玲~上课啦，这节课当然是最喜欢的体育课了，体育课前，我们都需要先按照从高到矮的顺序排成一排，先做好热身运动，才能开始自由活动。

排队

刚刚从教室下来，大家都跟同桌或者玩的比较好的同学站在一起，此时你们的站位还是随意的。

选择排序的思想

选择排序体现在先选择一个位置，再遍历队列找到符合条件符的同学，再将符合条件的同学与选中位置的同学交换位置，完成一轮比较。

当老师下达列队指令的时候，先选择最左边的位置，然后同学们从左至右分别报出自己的身高，并记录最矮的同学的位置，到最右边的同学报完数之后，将本次最矮的同学与本轮的开始位置的同学交换位置。

第一轮排序

选择最左边的位置，并把这个位置的同学的身高标记为最小值，从这个同学开始，右边的同学分别报出自己的身高。

1,2,3位置同学都比160高，此时标记的最矮的同学还是0号位的同学，到4号位同学156低于0号位160，此时标记最矮的同学为4号位。

5,6号位同学均比4号位同学高，则第一轮最矮的同学为4号位156的同学，将0号位同学与4号位同学交换位置。

交换位置后，第一轮比较完成，0号位为最矮的同学。

第二轮比较

第二轮比较开始，第二轮需要决定的位置是1号位，将1号位170标记为除了0号位外最矮的同学，从1号位开始到最右边的同学，找到最矮的同学。

2,3均比1号位高，继续往右报数，4号位比170矮，切换本轮标记至4号位，且5,6也比4号位高，第二轮的最矮即为4号位的160。

第二轮交换完成后，0,1号位完成排序。

第n轮比较

重复比较步骤，通过先选定位置，再遍历找到符合本轮条件的数值的坐标，交换两者位置，即可完成队列的选择排序。

选择排序实现

public static void selectionSort(int[] arr) {
        int n = arr.length;
        // 外层循环标记当前的位置
        for (int i = 0; i < n - 1; i++) {
            // 将当前位置假设为最小值的位置
            int minIndex = i;
            // 内层循环为外层标识+1至最右端位置
            for (int j = i + 1; j < n; j++) {
                // 当右端值比标记值小时，更细最小值的位置
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            // 如果最小元素的索引与当前位置不同，则进行交换
            if (minIndex != i) {
                int temp = arr[minIndex];
                arr[minIndex] = arr[i];
                arr[i] = temp;
            }
        }
    }

选择排序时间复杂度分析

在选择排序中，外层循环需要执行 n-1 次（n 为数组的长度）。对于每一次外层循环，内层循环需要执行 n-i-1 次比较操作，其中 i 是外层循环的迭代变量。

因此总的比较次数为：(n-1) + (n-2) + ... + 1 = (n-1) * n / 2，即选择排序算法的时间复杂度可以表示为 O(n^2)。

而由于选择排序是选择位置后寻找符合条件的位置，无论数组是否有序，都需要进行相同次数的比较和交换操作，即时间复杂度都是O(n^2)。

选择排序在时间复杂度上不具备优势，但它的优点是实现简单、易于理解，并且不需要额外的空间。对于小型数组或者部分有序的数组，选择排序可能是一个合适的选择。

开始自由活动

列好队啦~热身运动已经做完，大家可以自由去活动啦！