排序--02---选择排序

选择排序

排序原理：

1. 每一次遍历的过程中，都假定第一个索引处的元素是最小值，和其他索引处的值依次进行比较，如果当前索引处的值大于其他某个索引处的值，则假定其他某个索引出的值为最小值，最后可以找到最小值所在的索引
2. 交换第一个索引处和最小值所在的索引处的值

   

   

代码实现：

public class SelectSort {
    public static void selectSort(int[] data) {
        System.out.println("开始排序");

        int arrayLength = data.length;
        for (int i = 0; i < arrayLength - 1; i++) {
            int minIndex = i;
            for (int j = i + 1; j < arrayLength; j++) {
                if (data[minIndex] - data[j] > 0) {
                    minIndex = j;
                }
            }
            if(minIndex != i){
                int temp = data[i];
                data[i] = data[minIndex];
                data[minIndex] = temp;
            }
            System.out.println(java.util.Arrays.toString(data));
        }
    }

    public static void main(String[] args) {
        int[] data = { 9, -16, 21, 23, -30, -49, 21, 30, 30 };
        System.out.println("排序之前：\n" + java.util.Arrays.toString(data));
        selectSort(data);
        System.out.println("排序之后：\n" + java.util.Arrays.toString(data));
    }
}

           

选择排序的不稳定性

DataWrap

public class DataWrap implements Comparable<DataWrap>{
    int data;
    String flag;
    public DataWrap(int data,String flag){
        this.data = data;
        this.flag = flag;
    }
    public String toString(){
        return data + flag;
    }
    //根据data实例变量来决定两个dataWrap的大小
    @Override
    public int compareTo(DataWrap dw) {
        return this.data > dw.data? 1 : (this.data == dw.data? 0 : -1);
    }
}
           

SelectSort2

public class SelectSort2 {
    public static void selectSort(DataWrap[] data) {
        System.out.println("开始排序");
        int arrayLength = data.length;
        for (int i = 0; i < arrayLength - 1; i++) {
            int minIndex = i;
            for (int j = i + 1; j < arrayLength; j++) {
                if (data[minIndex].compareTo(data[j]) > 0) {
                    minIndex = j;

                }
            }
            if(minIndex != i){
                DataWrap temp = data[i];
                data[i] = data[minIndex];
                data[minIndex] = temp;
            }
            System.out.println(java.util.Arrays.toString(data));
        }
    }

    public static void main(String[] args) {
        DataWrap[] data = { new DataWrap(5, "*"), new DataWrap(8, ""),
                new DataWrap(5, ""), new DataWrap(-49, ""),
                new DataWrap(30, "*"), new DataWrap(22, ""),
                new DataWrap(30, "") };
        System.out.println("排序之前：\n" + java.util.Arrays.toString(data));
        selectSort(data);
        System.out.println("排序之后：\n" + java.util.Arrays.toString(data));
    }
}

           

5* 本来在5 之前,排序完,在新数组中,排到5后面去了.

我们知道第一遍选择第1个元素5会和-49交换，那么原序列中2个5的相对前后顺序就被破坏了，所以选择排序不是一个稳定的排序算法。

时间复杂度分析:

选择排序使用了双层for循环，其中外层循环完成了数据交换，内层循环完成了数据比较，所以我们分别统计数据

平均情况：T(n) = O(n2)

• 最佳情况：T(n) = O(n2)
• 最差情况：T(n) = O(n2)
• 平均情况：T(n) = O(n2)

对比: 冒泡排序和选择排序

1. 冒泡排序是比较相邻位置的两个数，而选择排序是按顺序比较，找最大值或者最小值；
2. 冒泡排序每一轮比较后，位置不对都需要换位置，选择排序每一轮比较都只需要换一次位置；
3. 冒泡排序是通过数去找位置，选择排序是给定位置去找数；

冒泡排序优缺点：

• 优点:

  比较简单，空间复杂度较低，是稳定的；

• 缺点:

  时间复杂度太高，效率慢；

选择排序优缺点：

• 优点：

  一轮比较只需要换一次位置；

• 缺点：

  效率慢，不稳定