冒泡排序(Bubble Sort)，是一種簡單的交換排序算法影钉。
原理：
- 相鄰元素比較后画髓，小的浮起來，大的沉下去平委。
- 每次外循環(huán)都至少有一個(gè)元素完成排序雀扶。
- 持續(xù)重復(fù)比較，未排序元素越來越少，直到?jīng)]有元素需要比較愚墓。
舉例：
輸入：nums = {2, 4, 7, 3, 1}
| 循環(huán)次數(shù)/下標(biāo) | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| 0 | 2 | 4 | 7 | 3 | 1 |
| 1 | 2 | 4 | 3 | 1 | 7 |
| 2 | 2 | 3 | 1 | 4 | 7 |
| 3 | 2 | 1 | 3 | 4 | 7 |
| 4 | 1 | 2 | 3 | 4 | 7 |
- 冒泡第一版：
void bubbleSort(vector<int>& nums){
for(int i = 0; i < nums.size() - 1; ++i){
for(int j = 0 ; j < nums.size() - 1 - i; ++j){// 每次外循環(huán)至少有一個(gè)元素完成排序
if(nums[j] > nums[j + 1])
swap(nums[j], nums[j + 1]);
}
}
}
這里我們可以思考一下予权，這個(gè)算法是否可以優(yōu)化呢？
答案是肯定的浪册，上面的例子可能體現(xiàn)不出來扫腺，如果我們的輸入數(shù)組的數(shù)據(jù)情況是：nums = {1, 2, 3, 4, 7, 5, 6, 8}，這里其實(shí)只要外循環(huán)一次就能解決問題村象。如何優(yōu)化這個(gè)冗余重復(fù)比較的過程呢笆环？引入一個(gè)變量來記錄是否發(fā)生交換，如果沒發(fā)生則可以退出循環(huán)了厚者。
- 冒泡第二版：
void bubbleSort(vector<int>& nums){
for(int i = 0; i < nums.size() - 1; ++i){
// 記錄是否沒發(fā)生交換
bool flag = true;
for(int j = 0; j < nums.size() - 1 - i; ++j){
if(nums[j] > nums[j + 1]){
flag = false;
swap(nums[j], nums[j + 1]);
}
}
// 如果沒發(fā)生交換躁劣，則退出
if(flag == true)
return;
}
}
在第二版后，我們再來思考一下库菲，是否能繼續(xù)優(yōu)化呢账忘？
如果想不出？我們可以舉個(gè)例子：nums = {2, 1, 4, 3, 5, 6, 7, 8, 9}熙宇，在這個(gè)例子中你會發(fā)現(xiàn)數(shù)組后半部分是有序鳖擒，所以前面兩種算法前5次有冗余比較。
- 冒泡第三版：
void bubbleSort(vector<int>& nums){
// 邊界烫止，右邊有序
int border = nums.size() - 1;
for(int i = 0; i < nums.size() - 1; ++i){
bool flag = true;
// 記錄發(fā)生最后一次交換的下標(biāo)
int last = 0;
for(int j = 0; j < border; ++j){
if(nums[j] > nums[j + 1]){
last = j;
flag = false;
swap(nums[j], nums[j + 1]);
}
}
border = last;
if(flag == true)
return;
}
}
最后
思考在兩次優(yōu)化后蒋荚，冒泡算法是否還能優(yōu)化呢？
