選擇排序
前言
原理：每次回圈對比找出最小/大值，將最值的元素交換至左側
思想：直接選擇排序（Straight Select Sort）演算法思想：第一趟從n個元素的資料序列中選出關鍵字最小/大的元素并放在最前/后位置，下一趟從n-1個元素中選出最小/大的元素并放在最前/后位置，以此類推，經過n-1趟完成排序
案例分析：
1、初始的無序數列 {5,8,6,3,1,7}，希望對其升序排序
2、按照思路分析：
內層回圈經過一輪對比后找到最小值，min = 1，下標為 index = 4；交換位置
代碼實作
第 1 版代碼
public static void straightSelectSort(int[] arr){
//i不需要 = 陣列最尾部元素，因為后面沒有值對比了
for (int i = 0; i < arr.length - 1; i++) {
//設定每次回圈的起始點為最小/大值
int min = arr[i];
//記錄下最小/大值的下標
int index = i;
for (int j = i + 1; j < arr.length; j++) {
//升序排序>,降序排序<
if (min > arr[j]){
min = arr[j];
index = j;
}
}
//一輪對比完成后，將默認的最小值賦予到找到的最值下標位置
arr[index] = arr[i];
//把找到的真實最值放到前面
arr[i] = min;
}
}
這里其實有可能出現默認的最小值其實就是真正的最小值，所以一輪內層回圈下來，是沒有交換資料，可以添加哨兵，如果沒有找到最小值，就不進行值的交換，減少交換次數，
第 2 版代碼
public static void straightSelectSort(int[] arr){
//i不需要 = 陣列最尾部元素，因為后面沒有值對比了
for (int i = 0; i < arr.length - 1; i++) {
//設定每次回圈的起始點為最小/大值
int min = arr[i];
//記錄下最小/大值的下標
int index = i;
//哨兵，記錄是否找到最值，默認false
boolean isSwap = false;
for (int j = i + 1; j < arr.length; j++) {
//升序排序>,降序排序<
if (min > arr[j]){
min = arr[j];
index = j;
//找到最值，設定為true
isSwap = true;
}
}
if (isSwap){
//一輪對比完成后，將默認的最小值賦予到找到的最值下標位置
arr[index] = arr[i];
//把找到的真實最值放到前面
arr[i] = min;
}
}
}
直接選擇排序演算法復雜度分析：
如果陣列中有**n個元素
第1輪回圈是arr[0] 和arr[1] ...arr[n-1] 進行比較，次數為n-1 次，arr[0]放最值，
第2輪回圈是arr[1] 和 arr[2]...arr[n-1] 進行比較，次數為n-2次，arr[1]放第二個最值，
所以不難得出它的比較的次數是n-1 + n-2 + n-3 + ....1 = n*（n-1）/2 ，
時間復雜度為 = n^2/2- n/2 = n^2 ,O（n^2），
演算法升級
分析
直接選擇排序每一次查找只是找出最小值，可以這么改進，查找最小值的同時，找到一個最大值，然后將兩者分別放在它們應該出現的位置，這樣遍歷的次數就會減少，同時添加哨兵，如果沒有找到最值，不發生交換
以新的無序數列 {5,1,6,3,9,2,7,0}為例，按照上面的分析，初始狀態如下：
排序程序如下：
交換最值，將最小值放到arr[left],最大值放到arr[right]，同時left++，right--；準備下一輪回圈，第一輪結果如下：
演算法注意點：
(1) 第二輪開始對比前，我們可以發現，此時arr[left]與arr[right]恰好是此輪的最值，因此應該加上哨兵，對此情況，內回圈走完后，不進行值交換，判斷條件：min == right && max == left
(2) 特別注意的地方：第三輪回圈后，可以發現的點是，left = 2,right = 5,而結果是min = 5,max = 2,仔細看你就發現了，left與min對應，而max與right對應，結果是值反面的的，所以在進行值交換的時候，進行一次就可以了，否則交換兩次，就變成了巴黎鐵塔翻過來又翻回去了，判斷條件：min == right && max == left
進化版代碼
public static void betterSelectSort(int[] arr) {
//left指標指向無序邊界起點，right指標指向終點，temp用作臨時變數交換值
int left,right,temp;
//默認指向無序串列起點
left = 0;
//默認指向無序串列終點
right = arr.length - 1;
//記錄每輪找到的最小值的下標
int min = left;
//記錄每輪找到的最大值的下標
int max = right;
//當right >= left時，串列已經有序
//記錄回圈的次數
int index = 0;
while(left < right) {
min = left; //每輪開始前，默認無序串列起點為最小值
max = right; //每輪開始前，默認無序串列終點為最大值
//指標i從左往右掃描，找出最小值，最大值
for (int i=left; i<=right; i++) {
if (arr[i]<arr[min]) {
min = i; //通過比較，記錄最小值的下標
}
if(arr[i]>arr[max]) {
max = i; //通過比較，記錄最大值的下標
}
}
index++;
if (min == left && max == right){
System.out.println("第" + index + "輪回圈沒有找到最值，無需交換");
}else if (min == right && max == left){
//交換一次即可，交換兩次的話，序列翻轉，相當于沒有交換
temp = arr[left];
arr[left] = arr[min];
arr[min] = temp;
}else {
//找到最小值，交換
temp = arr[left];
arr[left] = arr[min];
arr[min] = temp;
//找到最大值，交換
temp = arr[right];
arr[right] = arr[max];
arr[max] = temp;
}
//確定最小/大值，指標向中間移動
left++;right--;
}
}
優化后代碼雖然有效的減少了外層回圈的次數，但其時間復雜度仍然是O（n^2）
文章為原創，轉載請宣告出處
更多文章，歡迎點贊關注，我的掘金：https://juejin.im/user/1151943919304840/posts
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/8372.html
標籤：其他
上一篇：二維陣列中的查找