public class SelectSort {

    public static int[] selectSort(int[] arr) {

        // 数组长度小于 2 直接返回

        if(arr == null || arr.length < 2){

            return arr;

        }

        int n = arr.length; // 获取数组长度

        // 选择排序

        for (int i = 0; i < n - 1; i++) { // 从数组左向右循环 (最后一个数没有比较的意义，它已经经过替换是有序的)

            int min = i; // 获取当前位置下标

            for (int j = i + 1; j < n; j++) { // 循环从当前位置后一位开始到数组最右边 (一定会循环至最后一位)

                if (arr[min] > arr[j]) min = j; // 对比找到最小数的小标 (与下面直接交换位置导致算法不稳定原因)

            }

            // 交换位置

            int temp = arr[i];

            arr[i] = arr[min];

            arr[min] = temp;

        }

        // 插入排序

        for (int i = 0; i < n; i++) { // 从数组左向右循环 (到最后一个数)

            int data = arr[i]; // 获取当前位置数据

            for (int j = i; j > 0; j--){ // 循环从当前位置往数组起点出发 (概率最好是第一次循环就条件满足)

                if(data >= arr[j-1]){ // 因为从小往大排序，需确保数据放当前位置大于该位置前一个数

                    arr[j] = data; // 条件满足，数据放当前位置

                    break; // 退出本次循环

                } else {

                    arr[j] = arr[j-1]; // 条件不满足，当前位置前一个数移动到当前位置。(算法稳定原因)

                }

            }

        }

        // 冒泡排序

        for (int i = 0; i < n-1; i++) { // 从数组左向右循环 (最后一个数没有比较的意义，它已经经过替换是有序的)

            boolean flag = true; // 判断是否有过位置交换

            for (int j = n-1; j > i; j--){ // 循环从最右边往当前位置点出发 (概率最好是第一次循环就条件满足)

                if(arr[j] < arr[j-1]){ // 因为从小往大排序，需确保数据放当前位置大于该位置前一个数

                    // 交换位置 (算法稳定原因)

                    int temp = arr[j];

                    arr[j] = arr[j-1];

                    arr[j-1] = temp;

                    flag = false; // 有过位置交换，就不能保证数据有序，需要继续循环，如 4 与 8 交换，但 8 还在 5 前面。

                }

            }

            if(flag){ // 没有过位置交换，退出循环。因为剩余数字每个数都大于它前一个数，所以才没有交换位置发生

                break;

            }

        }

        return arr;

    }

}