選擇排序
選擇排序是一種簡單的排序算法。此排序算法是一種基于就地比較的算法，其中，清單分為兩部分，左端為已排序部分，右端為未排序部分。最初，已排序部分為空，未排序部分為整個清單。
從未排序的數組中選擇最小的元素，并與最左邊的元素交換，該元素成為排序數組的一部分。此過程繼續将未排序的數組邊界向右移動一個元素。
該算法不适用于大型資料集，因為其平均和最壞情況下的複雜度均為Ο(n^2)，其中n是項數。
核心思想
以下面描述的數組為例。
對于排序清單中的第一個位置，将順序掃描整個清單。目前存儲14的第一個位置，我們搜尋整個清單，發現10是最低值。
是以，我們将10替換為14。一次疊代10（恰好是清單中的最小值）出現在已排序清單的第一位置。
對于第二個位置（33個位置），我們開始以線性方式掃描清單的其餘部分。
我們發現14是清單中第二低的值，它應該出現在第二位。我們交換這些值。
經過兩次疊代後，兩個最小值以排序的方式位于開頭。
以下是整個分類過程的圖示-
代碼開發
實作思路
Step 1 − 設定最小值到位置0
Step 2 − 搜尋清單中的最小元素
Step 3 − 在MIN位置交換值
Step 4 − 遞增MIN以指向下一個元素
Step 5 − 重複直到清單排序
僞代碼
package com.paal.demo.c01SortingBasic;
import com.paal.demo.Sort;
import com.paal.demo.utils.SortTestHelper;
/**
* <p/>
* <li>title: 基礎排序-選擇排序</li>
* <li>@author: li.pan</li>
* <li>Date: 2019/11/4 12:43 下午</li>
* <li>Version: V1.0</li>
* <li>Description: </li>
*/
public class SelectionSort implements Sort {
@Override
public void sort(Integer[] arr) {
for (int i = 0; i < arr.length; i++) {
// 儲存最小元素所在位置
int minIndex = i;
for (int j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
// 自定義的用于數組元素交換的函數
SortTestHelper.swap(arr, i, minIndex);
}
}
}
/**
* 選擇排序測試
*/
@Test
public void selectionSortTest() {
Integer[] integers0 = SortTestHelper.generateRandomArray(100, 0, 1000000);
Integer[] integers1 = SortTestHelper.generateRandomArray(10000, 0, 1000000);
Integer[] integers2 = SortTestHelper.generateRandomArray(100000, 0, 1000000);
System.out.println("------------------------------随機數組--------------------------------");
System.out.println("選擇排序測試1"+SortTestHelper.testSort(integers0, new SelectionSort()));
System.out.println("選擇排序測試2"+SortTestHelper.testSort(integers1, new SelectionSort()));
System.out.println("選擇排序測試3"+SortTestHelper.testSort(integers2, new SelectionSort()));
}