七大排序之直接选择排序

目录

1、基本思想

2、代码讲解和实现

3、特性总结

---

时间复杂度：

空间复杂度：

稳定性： 不稳定

1、基本思想

        直接选择排序是选择排序的一种，其思想就是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。

2、代码讲解和实现

        跟插入排序一样，直接选择排序也是双循环，不过有区别的是选择排序外循环和内循环都是从前往后遍历数组。

        假设以遍历 i,和j 分别代表外内循环的变量，i 从 0 小表循环到 (array.length-2) 下标，i 每变化一次，j 就从 i+1下标 循环到  （array.length-1）下标。

        创建一个变量 minIndex 记录 每次循环中的最小值的下标，外循环每循环一次，就把 i 赋值给 minIndex。然后内循环找 i 下标之后的最小值，并把最小值的下标 赋值该 minIndex。

        最后交换 i下标 和 minIndex下标的值。一直重复上述操作，直到外循环结束。

    public static void selectSort(int[] array){
        for(int i =0 ; i< array.length-1;i++){
            //每次将 i 下标的 值 当做是 最小值
            int minIndex = i;
            for (int j = i+1; j < array.length; j++) {
                if(array[j] < array[minIndex]){
                    minIndex = j;
                }
            }
            swap(array,i,minIndex);
        }
    }

    /**
     * 交换函数
     * @param array
     * @param x
     * @param y
     */
    private static void swap(int[] array,int x,int y){
        int tmp = array[x];
        array[x] = array[y];
        array[y] = tmp;
    }

3、特性总结

   1. 直接选择排序思考非常好理解，但是效率不是很好。实际很少使用

   2. 直接选择排序对数据不敏感，不管是有序还是无序，时间复杂度都是这样 为

   3. 直接选择排序是内部排序，空间复杂度为

   4. 直接选择排序是一个不稳定的排序