选择排序

定义

从待排序的数据元素中选出最小（或最大的一个元素），存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。
以此类推，直到全部待排序的数据元素的个数为0.

稳定性

不稳定

时间复杂度

O(N²)

代码

测试用例

int arr[] = {2,4,3,1,6,5};

交换函数

    /**
     * 交换函数
     * @param arr
     * @param i
     * @param j
     */
    public static void swap(int[] arr,int i ,int j){
        int temp = arr[j];
        arr[j] = arr[i];
        arr[i] = temp;
    }

原代码

    /**
     * 选择排序
     * @param arr
     * @param len
     */
    public static void selectSort(int arr[],int len){
        int minIndex; // 记录最小元素的下标
        // 极限是倒数第二个元素
        for (int i = 0;i<len-1;i++){
            System.out.println("\n第"+(i+1)+"轮");
            minIndex = i;
            // 极限是最后一个元素
            for (int j = i+1;j<len;j++){
                if (arr[minIndex]>arr[j]){
                    minIndex = j; // 更新最小元素下标
                    System.out.println("较小元素:["+arr[minIndex]+"]； 较小元素下标:"+minIndex);
                }
            }
            // 将较小的元素放到前面 达到排序目的
            swap(arr,i,minIndex);
            System.out.println("第"+(i+1)+"次交换：" + Arrays.toString(arr));
        }
    }

运行结果
在这里插入图片描述

优化

每轮遍历会找出最大值和最小值然后将其放到按照排序应放置的位置，下一轮循环的时候，已经处理过的值（首尾）不会再被遍历到
以i记录每次开始遍历的位置 前i个和后i个都不会被遍历到，因为在上轮遍历中已经有序
这样可以减少将近一半的循环遍历

    /**
     * 选择排序
     * 第一次优化
     * 找出最大最小值
     * 每轮循环都会将首尾排好
     * @param arr
     * @param len
     */
    public static void selectSortOptimize1(int arr[],int len){
        System.out.println("初始状态 " + Arrays.toString(arr));
        int minIndex = 0; // 记录较小值的下标
        int maxIndex = 0; // 记录较大值的下标
        // 极限是倒数第二个元素
        for (int i = 0;i<len/2;i++){
            System.out.println("\n第"+(i+1)+"轮");
            minIndex = i; // 本轮较小元素目标位置
            maxIndex = len-1-i; // 本轮较大元素目标位置
            // 极限是最后一个元素
            for (int j = i+1;j<len-i;j++){
                if (arr[minIndex]>arr[j]){
                    minIndex = j; // 更新较小元素下标
                }
                if (arr[maxIndex]<arr[j]){
                    maxIndex = j; // 更新较大元素下标
                }
            }
            System.out.println("较小元素:["+arr[minIndex]+"]； 较小元素下标:"+minIndex);
            System.out.println("较大元素:["+arr[maxIndex]+"]； 较大元素下标:"+maxIndex);

            swap(arr,i,minIndex); // 将较小的元素放到前面 达到排序目的
            swap(arr,len-1-i,maxIndex); // 将较大的元素放到后面 达到排序目的
            System.out.println("第"+(i+1)+"次交换：" + Arrays.toString(arr));
        }
    }