JAVA十大排序算法之選擇排序詳解

更新時間：2021年08月23日 09:40:35 投稿：BJT

這篇文章主要介紹了java中的選擇排序，本文給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值，需要的朋友可以參考下

選擇排序

1.找到數(shù)組中最大（或最小）的元素

2.將它和數(shù)組的第一個元素交換位置（如果第一個元素就是最大（?。┰啬敲此秃妥约航粨Q）

3.在剩下的元素中找到最大（?。┑脑兀瑢⑺c數(shù)組的第二個元素交換位置。如此往復，直到將整個數(shù)組排序。

代碼實現(xiàn)

對下面數(shù)組實現(xiàn)排序：{87, 23, 7, 43, 78, 62, 98, 81, 18, 53, 73, 9}

動圖演示

選擇排序

代碼實現(xiàn)

public class SelectionSort {
    public static final int[] ARRAY = {87, 23, 7, 43, 78, 62, 98, 81, 18, 53, 73, 9};
    public static int[] sort(int[] array) {
        if (array.length == 0) {
            return array;
        }
        for (int i = 0; i < array.length; i++) {
            //最小數(shù)的下標，每個循環(huán)開始總是假設第一個數(shù)最小
            int minIndex = i;
            for (int j = i; j < array.length; j++) {
                //找到最小索引
                if (array[j] < array[minIndex]) {
                    //保存最小索引
                    minIndex = j;
                }
            }
            //最小索引的值
            int temp = array[minIndex];
            array[minIndex] = array[i];
            array[i] = temp;
        }
        return array;
    }
    public static void print(int[] array) {
        for (int i : array) {
            System.out.print(i + "  ");
        }
        System.out.println("");
    }
    public static void main(String[] args) {
        print(ARRAY);
        System.out.println("============================================");
        print(sort(ARRAY));
    }
}

時間復雜度

很明顯，和冒泡排序相比，在查找最小（或最大）元素的索引，比較次數(shù)仍然保持為O(n2)

，但元素交換次數(shù)為O(n)。

算法穩(wěn)定性

選擇排序是給每個位置選擇當前元素最小的，比如給第一個位置選擇最小的，在剩余元素里面給第二個元素選擇第二小的，依次類推，直到第n-1個元素，第n個元素不用選擇了，因為只剩下它一個最大的元素了。那么，在一趟選擇，如果一個元素比當前元素小，而該小的元素又出現(xiàn)在一個和當前元素相等的元素后面，那么交換后穩(wěn)定性就被破壞了。舉個例子，數(shù)組5，8，5，2，9，我們知道第一遍選擇第1個元素5會和2交換，那么原序列中兩個5的相對前后順序就被破壞了，所以選擇排序是一個不穩(wěn)定的排序算法。