手把手教你搞懂冒泡排序和選擇排序
冒泡排序
原理：
從頭（左邊）開始比較每一對相鄰的元素，如果第1個比第2個大，就交換它們的位置，執行完一輪後，最末尾（最右邊）就是最大的元素。
舉例：
假設存在數組nums={6，8，2，9，4}，對nums數組進行排序
從左往右開始，拿出兩個元素進行對比，出現兩種情況：
1.左邊元素 <= 右邊元素，不變
2.左邊元素 > 右邊元素，交換他們的位置（這裡可以寫成>=嗎？不行，因為會造成排序不穩定）
接下來就是新的一輪排序，邏輯跟上圖的流程是一樣的，不同的是會將最大的元素排除在外，不用進行比較。
手撕代碼：
/*
沒有使用過優化策略的冒泡排序
*/
public class BubbleSort1 {
//測試數據
public static int[] nums = {4,1,7,11,9,55};
//main方法
public static void main(String[] args){
//這個for循環每循環完一次，end--，說明就把最大的元素給選出來瞭
for (int end = nums.length - 1; end > 0; end--){
for (int begin = 1; begin <= end; begin++){
if(nums[begin] < nums[begin - 1]){ //每當發現左邊的元素大於右邊的元素
//交換元素
int temp = nums[begin];
nums[begin] = nums[begin - 1];
nums[begin - 1] = temp;
}
}
}
//打印驗證結果
for(int num : nums){
System.out.print(num+"_");
}
}
}
時間復雜度為O（n^2），也就是n的平方，不過這是平均時間復雜度
存在最好時間復雜度O（n），那就是數組本來就有序，也就是說隻掃描一遍就行瞭。
優化策略：
由於存在部分有序的情況，例如nums數組為{8，5，2，10，11，12}，也就是說10，11，12都沒有比較的必要瞭
優化代碼：
/*
使用過優化策略的冒泡排序
*/
public class BubbleSort1 {
public static int[] nums = {4,1,7,11,9,55};
public static void main(String[] args){
for (int end = nums.length - 1; end > 0; end--){
int sortIndex = 1; //記錄最後一次交換位置
for (int begin = 1; begin <= end; begin++){
if(nums[begin] < nums[begin - 1]){
int temp = nums[begin - 1];
nums[begin - 1] = nums[begin];
nums[begin] = temp;
sortIndex = begin;
}
end = sortIndex;
}
}
for(int num : nums){
System.out.print(num+"_");
}
}
}
選擇排序
原理：
從數組中找到最大的元素，然後與末尾（最右邊）的元素交換位置，執行完一輪後，末尾（最右邊）的那個元素就是最大的元素。
舉例：
假設存在數組nums={5，8，1，9，3}，對nums數組進行排序，準備一個maxIdex代表當前最大元素的下標
接下來就是新的一輪排序，邏輯跟上圖的流程是一樣的，不同的是會將最大的元素排除在外，不用進行比較。
手撕代碼：
/**
* 選擇排序
*/
public class SelectionSort {
//測試數據
private static int[] nums = {6,3,2,8,9};
//main方法
public static void main(String[] args){
//這個for循環每循環完一次，end--，說明就把最大的元素給選出來瞭
for(int end = nums.length - 1; end > 0; end--){
int maxIndex = 0; //假設下標0是數組中最大元素
for(int begin = 1; begin <= end; begin++){ //從左往右開始比較
if(nums[maxIndex] < nums[begin]){ //發現存在一個元素大於假設最大元素
maxIndex = begin; //更改最大元素索引
}
}
//最右邊一個元素和最大值元素交換位置
int temp = nums[maxIndex];
nums[maxIndex] = nums[end];
nums[end] = temp;
}
//打印結果
for(int num : nums){
System.out.print(num+"_");
}
}
}
總結
本篇文章就到這裡瞭，希望能給你帶來幫助，也希望您能夠多多關註WalkonNet的更多文章！