面試必備：經典演算法影片決議之選擇排序
哈嘍，我是程式員大鵬，
上一篇我們介紹了經典演算法影片決議系列：冒泡排序，今天我們再介紹另外一個經典的排序演算法簡單選擇排序，簡單選擇排序也叫直接選擇排序，是最基本的選擇排序方法，
選擇排序思想
基本思想
實作思想是每步從排序記錄中選出排序碼最小（最大）的記錄，放在已排序記錄序列的最后（前）；
演算法特點
直接選擇排序演算法n個記錄的檔案的直接選擇排序可經過n-1趟直接選擇排序得到有序結果，
排序原理
- 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置
- 再從剩余未排序元素中繼續尋找最小（大）元素，然后放到已排序序列的末尾，
- 重復第二步，直到所有元素均排序完畢，
選擇排序影片
選擇排序代碼
public static void selectionSort(int[] arr) {
int min, temp;
for (int i = 0; i < arr.length ; i++) {
// 初始化最小下標為最小資料陣列下標
min = i;
for (int j = i + 1; j < arr.length; j++) {
// 在未排序元素中繼續尋找最小元素，并保存其下標
if (arr[j] < arr[min]) {//如果有小于當前最小值的值
min = j;//將此數值的下標賦值給min
}
}
if (min != i) {// 如果min不等于i，說明找到最小值，進行交換
//資料交換
temp = arr[min];
arr[min] = arr[i];
arr[i] = temp;
}
}
}
讓我們來一行一行地分析一下代碼：
for (int i = 0; i < arr.length ; i++) {
在上面代碼是外層回圈，在剛開始的時候，先記錄下來當前最小值的索引，也就是i的值，
min = i;
每一輪開始的時候，min的值就是起點的索引，也就是未排序資料的起始索引，第一輪為0，第二輪是1,第三輪是2，依次類推，一直到最后一輪，
for (int j = i + 1; j < arr.length; j++) {
開始內層的回圈
if (arr[j] < arr[min]) {
min = j;
}
依次檢查未排序的資料，如果遇到的值比索引為min的值小，則將min更新為這個資料的索引，當內層回圈完畢時，min就是是當前輪的最小值的索引，
if (min != i) {
temp = arr[min];
arr[min] = arr[i];
arr[i] = temp;
}
判斷min與初始值i比較，如果不一樣，說明最小值不是第一個，則將索引為i的值與索引為min的值進行交換，
選擇排序復雜度分析
容易看出，待排序序列為正序，移動次數最小，為 0 次；待排序序列為逆序時，移動次數最多，為 3(n-1) 次，
但無論記錄的初始排列如何，關鍵碼的比較次數相同，第 i 趟排序需進行 n-i 次關鍵碼的比較，而簡單選擇排序需要進行 n-1 趟排序，因此，總的比較次數為 O(n^2)
故而，無論是最優、最差時間復雜度，還是平均時間復雜度，均為 O(n^2)
對于空間復雜度來說，簡單選擇排序僅需一個存盤空間用于記錄交換的暫存單元，即空間復雜度為 O(1)
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/63379.html
標籤：Java