廢話不多說先上代碼
void bubbleSort(int arr[], int length) {
int temp;
int flag = 1;
for(int i = 1; i < length; ++i) {
if(flag == 0)
break;
flag = 0;
for(int x = 0; x < length - i; ++x) {
if(arr[x] > arr[x + 1]) {
temp = arr[x];
arr[x] = arr[x + 1];
arr[x + 1] = temp;
flag = 1;
}
}
}
return;
}
時間復雜度
O(n2)
空間復雜度
O(1) 原地排序
穩(wěn)定排序
是穩(wěn)定排序
算法核心思想
假設要排序的數(shù)組的下標為0 到 5舷暮。下面所有的數(shù)字都代表其下標在數(shù)組中對應的數(shù)。
比較 0 和 1悼吱，如果 0 大于 1 就交換他們的位置呜魄，然后對比 1 和 2，如果 1 大于 2 就交換他們的位置步绸，以此類推尝丐。
一輪要比較多少次呢显拜？答案是數(shù)組長度減1次，這個比較次數(shù)可以隨著輪次的增加而減少爹袁，因為每一輪比較和交換過后远荠，最后的數(shù)一定是最大的數(shù)。
一共要進行多少輪呢失息？答案是數(shù)組長度減1次譬淳。這個次數(shù)是固定的，但是我們可以加入flag標記盹兢，如果數(shù)組已經(jīng)有序了就跳出循環(huán)邻梆。
一步一步實現(xiàn)冒泡排序
內(nèi)層循環(huán)，實現(xiàn)對比交換每個數(shù)字蛤迎。
void bubbleSort(int arr[], int length) {
int temp;
//我每次拿 i 和 i + 1 進行比較确虱，當 i 等于 length 的時候 i + 1 就已經(jīng)越界了（超出長度限制含友，所以我們循環(huán)只到 length - 1）
for(int i = 0; i < length - 1; ++i) {
//如果前面的數(shù)大于后面的數(shù) 就交換位置
if(arr[i] > arr[i + 1]) {
temp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = temp;
}
}
}
//一輪循環(huán)結(jié)束后替裆，最大的已經(jīng)在最后了
外層循環(huán)
因為內(nèi)層循環(huán)一輪只能把一個最大的數(shù)放在最后校辩，所以我們還有進行多次內(nèi)層循環(huán)。
void bubbleSort(int arr[], int length) {
int temp;
//每次能將一個移動到最后辆童，那么一共需要進行 length - 1 次循環(huán)
for(int x = 0; x < length - 1; ++x) {
//我每次拿 i 和 i + 1 進行比較宜咒，當 i 等于 length 的時候 i + 1 就已經(jīng)越界了（超出長度限制，所以我們循環(huán)只到 length - 1）
for(int i = 0; i < length - 1; ++i) {
//如果前面的數(shù)大于后面的數(shù) 就交換位置
if(arr[i] > arr[i + 1]) {
temp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = temp;
}
}
}
}
//到此 簡單的冒泡排序就已經(jīng)結(jié)束了
細節(jié)優(yōu)化
這里我們可以優(yōu)化一些細節(jié)把鉴。
內(nèi)層循環(huán)次數(shù)故黑，外層循環(huán)次數(shù)
void bubbleSort(int arr[], int length) {
//使用flag 減少外層循環(huán)次數(shù) 如果數(shù)組經(jīng)過幾輪交換后就已經(jīng)有序了，這時我們可以跳出循環(huán);
int flag = 1;
int temp;
//每次能將一個移動到最后庭砍，那么一共需要進行 length - 1 次循環(huán)
for(int x = 1; x < length; ++x) {
//flag 等于 0 說明上輪循環(huán)沒有交換任何數(shù)據(jù)场晶，數(shù)組已經(jīng)有序了。
if(flag == 0)
break;
flag = 0;
//我每次拿 i 和 i + 1 進行比較怠缸，當 i 等于 length 的時候 i + 1 就已經(jīng)越界了（超出長度限制诗轻，所以我們循環(huán)只到 length - 1）
//因為每一輪循環(huán)都將最大的數(shù)放到了最后，就沒必要和最后的數(shù)進行比較了
//內(nèi)存循環(huán)的次數(shù)為 length - 1揭北、length - 2扳炬、length - 3 ……，這時我們可以借助外層循環(huán)的參數(shù)實現(xiàn)搔体。
for(int i = 0; i < length - x; ++i) {
//如果前面的數(shù)大于后面的數(shù) 就交換位置
if(arr[i] > arr[i + 1]) {
temp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = temp;
flag = 1;
}
}
}
}
// OK 優(yōu)化也已經(jīng)完成了
到此冒泡排序已經(jīng)結(jié)束了恨樟，你學會了嗎？
冒泡排序還是很簡單的疚俱，優(yōu)化這里只是稍稍有點繞而已劝术，加油~
記得點贊哦。
