排序演算法之選擇排序

• 2022 年 8 月 10 日
• 筆記
• 排序演算法

選擇排序(Selection Sort)

選擇排序(Selection-sort) 是一種簡單直觀的排序演算法。它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然後，再從剩餘未排序元素中繼續尋找最小（大）元素，然後放到已排序序列的末尾。以此類推，直到所有元素均排序完畢。

演算法描述

1. 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
2. 再從剩餘未排序元素中繼續尋找最小（大）元素，然後放到已排序序列的末尾。
3. 重複第二步，直到所有元素均排序完畢。

演算法分析

動圖演示

程式碼實現

public class SelectionSort {

    public static void swap(int[] array, int begin, int end){
        int temp = array[begin];
        array[begin] = array[end];
        array[end] = temp;
    }

    public static void sort(int[] array) {
        
        //存儲最大值得下標
        int maxIndex;
        for (int end = array.length - 1; end > 0; end--) {
            maxIndex = 0;
            for (int begin = 1; begin <= end; begin++) {
                if (array[maxIndex] <= array[begin]) {
                    //將當前下標賦值給 maxIndex
                    maxIndex = begin;
                }
            }
            //交換最大值
            swap(array,maxIndex,end);
            System.out.println("第" + (array.length - end) + "次排序： " + Arrays.toString(array));
        }
    }

    public static void main(String[] args) {
        int[] array = {5, 9, 7, 4, 1, 3, 2, 8};
        System.out.println("排序前： " + Arrays.toString(array));
        sort(array);
    }
}

執行結果：

與冒泡排序比較

1. 二者平均時間複雜度都是 $O(n^2)$
2. 選擇排序一般要快於冒泡，因為其交換次數少
3. 但如果集合有序度高，冒泡優於選擇
4. 冒泡屬於穩定排序演算法，而選擇屬於不穩定排序
   • 穩定排序指，按對象中不同欄位進行多次排序，不會打亂同值元素的順序
   • 不穩定排序則反之