選擇排序

1. 前言

本節(jié)內(nèi)容是排序算法系列之一：選擇排序，主要講解了選擇排序的主體思路，選取了一個待排序的數(shù)字列表對選擇排序算法進行了演示，給出了選擇排序算法的 Java 代碼實現(xiàn)，幫助大家可以更好的理解選擇排序算法。

2. 什么是選擇排序？

選擇排序（Select Sort），是計算機科學(xué)與技術(shù)領(lǐng)域中較為簡單的一種排序算法。

假設(shè)我們按照從小到大的順序進行排序。選擇排序會首先從待排序序列中選擇一個最小的元素放入排序好的序列中，然后依次在從未排序好的序列中選擇最小的元素，直到最后需要選擇的待排序序列中只有一個元素，只需要將這個元素放在最后位置，就完成了整個排序過程。

選擇排序的算法名稱的由來就是因為在排序的過程中，按照排序規(guī)則（升序或者降序），依次從待排序的序列中選擇出需要排列的元素。越小或者越大的元素會先選擇出來，直至完成整個排序。

3. 選擇排序過程

在介紹完選擇排序之后，我們一起來看一下選擇排序的實現(xiàn)步驟具體是什么樣的吧。這里我們假設(shè)待排序的序列為 [9,2,11,7,12,5]，我們按照從小到大的序列進行排序。

3.1 算法步驟

1. 步驟 1：

在待排序的序列中找到最小的元素，將最小元素與排序序列中首位元素交換位置；

偽代碼實現(xiàn)如下：

//待排序的序列記為A，尋找最小元素的偽代碼如下：
min = A[0]
for(int i=1;i<A.length;i++){
   if(A[i] < min){
     min = A[i]
   }
}

2. 步驟 2：

從剩余的未排序序列中，繼續(xù)找出一個最小元素，將最小元素與排序好的序列的下一個位置進行交換；

3. 步驟 3：

重復(fù)步驟 2 的工作，直至排序完成。

其實，選擇排序主要是靠步驟 2 的重復(fù)執(zhí)行，他會每次把最小的元素先選擇出來，然后放在排序好的序列的尾部。接下來，讓我們用上面的待排序數(shù)字序列 [9,2,11,7,12,5] 進行整個算法步驟的排序演示工作。

3.2 算法演示

按照 2.1 節(jié)的排序步驟，首先我們會找出排序數(shù)字序列 [9,2,11,7,12,5] 中的最小元素 2，將 2 看作是排序好的元素，放在排序好的序列首位，如下：

[9,2,11,7,12,5]   -->  [2,9,11,7,12,5]   //找出待排序序列中最小元素2，放在首位，所以與9交換了位置

接著，步驟 2，步驟 3 的描述，我們重復(fù)進行最小元素的選擇工作，整個過程如下：

[2,9,11,7,12,5]   -->  [2,5,11,7,12,9]	 //找出[9,11,7,12,5]中最小元素5，然后與9交換位置
[2,5,11,7,12,9]   -->  [2,5,7,11,12,9]	 //找出[11,7,12,9]中最小元素7，然后與11交換位置
[2,5,7,11,12,9]   -->  [2,5,7,9,12,11]	 //找出[11,12,9]中最小元素9，然后與11交換位置
[2,5,7,9,12,11]   -->  [2,5,7,9,11,12]   //找出[12,11]中最小元素11，然后與12交換位置
[2,5,7,9,11,12]   -->  [2,5,7,9,11,12]	 //最后一個元素12，已經(jīng)在排序好的位置上，排序完成

步驟 2 會依次從待排序的序列中選擇一個最小的元素出來，然后將最小元素與排序好的序列的下一個位置的元素進行互換。重復(fù)整個 步驟 2，直至最后待排序序列只剩下一個元素，最后一個元素已經(jīng)排序好，說明整個排序過程結(jié)束。

Tips: 步驟 2 中每次執(zhí)行選擇一個最小的元素時，都會在未排序序列的內(nèi)部進行一次比較篩選，記錄下最小元素的位置，當(dāng)遍歷完成整個待排序序列之后，就可以確定最小元素的位置，將最小元素與已排序好序列的下一個元素進行位置互換，就完成了一個選擇最小元素的過程。

從上面的示例可以看出，其實整個選擇排序的過程，每次都會去在未排序序列的內(nèi)部進行一次選擇，找出最小的元素，將未排序序列中最小元素放在排序好的序列的下一位置。重復(fù)執(zhí)行這個過程，就可以完成排序。

4. Java 代碼實現(xiàn)

在說明選擇排序的整個過程之后，接下來，我們看看如何用 Java 代碼實現(xiàn)選擇排序算法。

import java.util.Arrays;

public class SelectSort {

    public static void main(String[] args) {
        //初始化需要排序的數(shù)組
        int array[] = {9, 2, 11, 7, 12, 5};

        //依次進行選擇排序，每次找出最小的元素，放入待排序的序列中
        for(int i=0;i<array.length;i++){
            
            //記錄最小元素min和最小元素的數(shù)組下標(biāo)索引minIndex
            int min = array[i];
            int minIndex = i;

            //在未排序的序列中找出最小的元素和對應(yīng)數(shù)組中的位置
            for(int j=i+1;j<array.length;j++){
                if(array[j] < min){
                    min = array[j];
                    minIndex = j;
                }
            }
            
            //交換位置
            int temp = array[i];
            array[i] = array[minIndex];
            array[minIndex] = temp;
        }

        //打印出排序好的序列
        System.out.println(Arrays.toString(array));
    }

}

運行結(jié)果如下：

[2, 5, 7, 9, 11, 12]

代碼中的第 7 行初始化一個需要排序的數(shù)組，后面按照從小到大的排序規(guī)則，實現(xiàn)了數(shù)組的排序。第 10 行是外層 for 循環(huán)，不斷地重復(fù)選擇排序工作。第 17 行是內(nèi)層循環(huán)，不斷地實現(xiàn)每一次 “選擇 “，在未排序的序列中找出最小的元素和對應(yīng)數(shù)組中的位置。第 24 至第 27 行實現(xiàn)了將未排序好的序列中的最小元素與需要排序的位置的元素進行交換的功能。第 31 行打印出排序好的數(shù)組。

5. 小結(jié)

本節(jié)主要學(xué)習(xí)了選擇排序算法，在學(xué)完本節(jié)課程之后，需要熟悉選擇排序的算法流程，知道選擇排序算法的實現(xiàn)思路，可以自己用代碼實現(xiàn)選擇排序算法。至此，我們已經(jīng)學(xué)習(xí)了排序算法中的冒泡排序、插入排序、選擇排序，希望大家可以比較一下不同排序算法的實現(xiàn)思路，自己多總結(jié)思考。