本篇文章是千鋒長沙Java培訓分享之Java算法之選擇排序的講解：

一、排序和算法

排序是算法中的一部分，也叫排序算法。算法一般用來處理數據，而數據的處理最好是要找到他們的規律，這個規律中有很大一部分就是要進行排序，所以需要有排序算法。本節講解的是選擇排序，從選擇排序開始認識排序的一些基礎概念。之所以將選擇排序作為排序的入門，原因是選擇排序算法的邏輯最好理解。

二、選擇排序

2.1 選擇排序算法邏輯

選擇排序是一種最簡單的排序算法。其排序的邏輯如下：

1、有一個待排序的數組A（以下簡稱A）。

2、從A中找出最小的元素。

3、將找到的最小元素跟數組A中第一個元素交換位置（如果最小元素就是第一個元素，則自己跟自己交換位置）；如下圖：

(如上圖，長方形高低代表數字的大小，找到最小的數字，跟第一個位置的數據進行交換）

交換之后，結果如下圖所示：

4、然后，在剩下的4個數字中再找到最小的那個數字，跟第2個位置的數字交換。如下圖：

交換之后的結果如下如：

5、再在剩下的三個數字中，找到最小的那個數字跟第3個位置的數字交換位置。上圖中剩下的三個數字中最小的就是第3個位置的數字，所以，它自己跟自己交換位置，就是不變。同理第四個數字也是不變，第5個數字也是不變。（上圖中例子第3、4、5個元素正好就是對應的排序，所以不變。如果不是對應的最小數字，同理交換位置就行。）

以上就是選擇排序的算法邏輯，非常好理解。

2.2 選擇排序算法代碼實現

理解了選擇排序的邏輯之后，接下來通過java代碼實現選擇排序算法。步驟如下：

找出最小的數字

將最小的數字放到第一個位置

將第一個位置的數字，放到原本是最小數字的位置。

重復上面3個步驟

選擇排序java代碼如下：

/**

* 選擇排序

*/

public static void algorithm4(){

//定義一個整數類型數組，用于排序的原始數據

int[] array={3,5,1,2,4};

//獲取數組的大小

int length = array.length;

//第一個循環用來遍歷數組中的所有數字

for (int i = 0; i < length; i++) {

//初始化一個變量，用來記錄最小數字的下標。初始默認假設第一個數字就是最小數字

int minIndex = i;

//第二個循環，通過比較獲取數組中最小的數字的下標。

for (int j = i+1; j < length ; j++) {

//如果找到更小的數字，

if (array[minIndex]>=array[j]) {

//將minIndex變量的值修改為新的最小數字的下標。

minIndex = j;

}

}

//所有數字一個個比較結束之后，就能確認那個數字最小了。

//將最小的數字替換到第一個位置，將第一個位置的數字放到最小數字原來的位置，就是一次交換。

int temp=array[i];

array[i]=array[minIndex];

array[minIndex]=temp;

}

//將排序之后的數組打印出來。

//下面的輸出是不計算時間復雜度的，因為實際開發中這段輸出代碼會被刪掉

for (int i = 0; i < length; i++) {

System.out.print(array[i]+"，");

}

}

以上就是選擇排序的代碼實現。學習了前面的時間復雜度之后，大家可以計算一下選擇排序的時間復雜度是多少呢？

2.3、選擇排序的時間復雜度

選擇排序總共循環了所少次？

n+(n-1)+(n-2)+(n-3)+…+1

上述這個表達式，反過來寫就是1+2+3+4+5+…+n。高斯算法就是（n+1）n/2=(n^2+n)/2=1/2n^2+n/2。當n->∞時，利用極限思維1/2*n^2+n/2可以等于n^2，記作O(n^2)，也就是選擇排序的時間復雜度是O(n^2)。

總結：選擇排序是一種簡單的排序算法，適用于數據量較小的情況，因為根據時間復雜度分析，數據量越大，選擇排序所花費的時間按照平方倍數增長，會非常慢。但是選擇排序也有它的優勢，選擇排序的優勢就是思維邏輯簡單。

選擇排序還有個特點，就是不論數組的順序是排好序或者是亂序的，選擇排序都需要花費一樣的時間來計算。比如，利用選擇排序對數組{1,2,3,4,5}和數組{3,1,4,2,5}排序所花費的時間是一樣的。排序是算法中比較重要的內容，從簡單的入手，從易到難學習常見排序算法是一個比較好的方式。如果有疑問的歡迎大家留言討論。

上一篇

千鋒長沙前端培訓分享之vue組件緩存之keep-alive

下一篇

千鋒長沙前端培訓分享之初級前端面試題整理