排序-简单选择

写在前边的话：今天记录一下关于算法中简单选择排序的一些理解和心得。
主要分为以下几个方面分享

• 简单选择排序的思想
• 实现方式
• 时间复杂度
• 与冒泡排序的比较

---

简单选择排序的思想

1:给定一个具有n位数据的数组，拿 当前值与其后序列中的数据 进行比较， 如果此次遍历结束后发现 该序列中的最小(大)值比当前值还要小(大)，则交换2者的数据。
2:重复n-1次上述操作，直至该序列中所有数据满足降(升)序为止。

---

实现方式

    public static void main(String[] args){
        Integer[] array1 = Util.createRandomArray();
        Integer[] array2 = Arrays.copyOf(array1, array1.length);

        System.out.println("数据源：" + Arrays.toString(array1) + "---------------------------------");

        selectSort(array1);
        Util.print(array1 , "SelectSort");

        Util.test(array2);
        Util.print(array2, "Result    ");

    }

    /**
     * 简单选择排序
     * @param src 数据源
     */
    private static void selectSort(Integer[] src){
        Util.checkSrc(src);

        //参数说明
        //i:需要从"哪个位置"开始执行后续的操作,该位置之前的序列已经是有序的了
        //j:因为比较的是 i 和 其后序列中数的大小，所以 j初始化为i后一位
        //curMinIndex:记录该次循环中最小值的下标

        for(int i = 0; i < src.length; i++){         //n-1次循环
            int curMinIndex = i;                     //初始化 当前最小值位置下标 为i

            for(int j = i + 1; j < src.length; j++){ //swap循环。目的是为了找出:"从i位置开始的序列中最小的值"。
                if(src[curMinIndex] > src[j]){       //如果存在的话,记录此值的下标
                    curMinIndex = j;
                }
            }

            if(curMinIndex != i){                    //swap操作。交换 i与curMinIndex下标所对应的值
                int temp = src[i];
                src[i] = src[curMinIndex];
                src[curMinIndex] = temp;
            }
        }
    }

查看log

数据源：[27, 4, 16, 70, 74, 86, 20, 19, 42, 13]
SelectSort:4---13---16---19---20---27---42---70---74---86
Result    :4---13---16---19---20---27---42---70---74---86

---

时间复杂度

结论:O(n^2)

分析:假如有n=5个数要排序，总共需要执行n-1=4次循环操作
第1次：需要比较n-1=4次
第2次：需要比较n-2=3次
第3次：需要比较n-3=2次
第4次：需要比较n-4=1次

总共执行的次数为：n-1 + n-2 + ... + 2 + 1===>n^2/2，所以该排序的时间复杂度为:O(n^2)

---

与冒泡排序的比较

相同点：

1：时间复杂度都是O(n^2)。
2：一次循环只能确定出 一个最小(大)。

不同点：

结论
选择排序相较冒泡排序来说，时间复杂度虽然没有降低，但是减少了“数据交换”的次数。
原因
“简单选择排序”在swap循环中，如果发现有数据的值比当前值要小(大)，只是保存下该数据的下标，等该swap循环结束后再交换2者的值。
“冒泡排序”则是在swap循环中，如果发现有数据的值比当前值要小(大)，就直接交换。