資料結構與算法系列（三）—選擇排序

前言

大家好，牧碼心今天給大家推薦一篇資料結構與算法系列（三）—選擇排序的文章，希望對你有所幫助。大綱如下:

• 選擇排序基本介紹
• 選擇排序圖文說明
• 選擇排序時空複雜度和穩定性
• 選擇排序具體實作

選擇排序基本介紹

選擇排序 是一種較簡單的排序算法，排序過程類似于隊伍排隊，每次選出相對最高或最小的同學排列。相比于冒泡排序省去了每輪交換多次的開銷。其基本思想是：首先在未排序的數列中找到最小(or最大)元素，然後将其存放到數列的起始位置；接着，再從剩餘未排序的元素中繼續尋找最小(or最大)元素，然後放到已排序序列的末尾。以此類推，直到所有元素均排序完畢。

選擇排序圖文說明

• 下面以數列{20,40,30,10,60,50}為例，示範選擇排序過程

  

  排序流程說明：
  • 第1趟：i=0。找出a[1…5]中的最小值a[3]=10，然後将a[0]和a[3]互換。 數列變化：20,40,30,10,60,50 – > 10,40,30,20,60,50
  • 第2趟：i=1。找出a[2…5]中的最小值a[3]=20，然後将a[1]和a[3]互換。 數列變化：10,40,30,20,60,50 – > 10,20,30,40,60,50
  • 第3趟：i=2。找出a[3…5]中的最小值，由于該最小值大于a[2]，該趟不做任何處理。
  • 第4趟：i=3。找出a[4…5]中的最小值，由于該最小值大于a[3]，該趟不做任何處理。
  • 第5趟：i=4。交換a[4]和a[5]的資料。 數列變化：10,20,30,40,60,50 – > 10,20,30,40,50,60

選擇排序時空複雜度和穩定性

時間複雜度	空間複雜度	穩定性
O(n^2)	O(1)	不穩定

• 說明
  • 時間複雜度：選擇排序每一輪需要選出最小值min，在互動到最左邊的時間複雜度為O(n)，共需要進行n-1輪。是以總的時間複雜度為O(n^2) ；
  • 空間複雜度 ：選擇排序是原地排序，沒有産生額外的空間，則為O(1) ；
  • 穩定性 ：選擇排序是不穩定的，比如被排序的序列存在多個相同的的元素時，該排序會打亂各元素原有的相對順序。

選擇排序實作

• 選擇排序（java版）

/*
     * @Author:greekw
     * @Desc: 選擇排序，類比站隊
     * @Date 0:04 2020/7/22
     * @Param [array]
     * @return void
    **/
    public static void selectSort(int[] array){
        for (int i = 0; i < array.length ; i++) {
            // 設定初始的最小位置
            int minIndex = i;

            // 找出最小元素的位置
            for (int j = i; j < array.length; j++) {

                minIndex = (array[j] < array[minIndex]) ? j : minIndex;
            }

            // 交換元素，排序
            int temp = array[i];
            array[i] = array[minIndex];
            array[minIndex] = temp;
        }
    }
 	// 測試用例
    public static void main(String[] args) {
        int[] selectArray= new int[]{20,40,30,10,60,50};
        selectSort(selectArray);
        System.out.println(Arrays.toString(selectArray));
    }
 
           

歡迎關注我的公衆 号（牧碼心），擷取很多精彩文章和學習資料！