排序--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. 冒泡排序是通過數去找位置，選擇排序是給定位置去找數；

冒泡排序優缺點：

• 優點:

  比較簡單，空間複雜度較低，是穩定的；

• 缺點:

  時間複雜度太高，效率慢；

選擇排序優缺點：

• 優點：

  一輪比較隻需要換一次位置；

• 缺點：

  效率慢，不穩定