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

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

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

選擇排序

1.找到數(shù)組中最大（或最?。┑脑?/p>

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

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

代碼實(shí)現(xiàn)

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

動(dòng)圖演示

選擇排序

代碼實(shí)現(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ù)的下標(biāo)，每個(gè)循環(huán)開(kāi)始總是假設(shè)第一個(gè)數(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í)間復(fù)雜度

很明顯，和冒泡排序相比，在查找最?。ɑ蜃畲螅┰氐乃饕容^次數(shù)仍然保持為O(n2)

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

算法穩(wěn)定性

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