冒泡排序(BubbleSort)
應(yīng)該是最基礎(chǔ)的一個(gè)排序方法啦前联，大一老師就講過(guò)的喇勋，所以在我腦海中也是最熟的一個(gè)排序算法了.
冒泡排序顧名思義，在每躺冒泡中别凤，大的關(guān)鍵字像石頭一樣“沉底”饰序，小的關(guān)鍵字像氣泡一樣逐漸向上“浮動(dòng)”，最終使得整個(gè)序列有序（這個(gè)概念解釋好蒼白hhhhh）
代碼：
#include <iostream>
using namespace std;
void BubbleSort(int array[], int n) {
int i, j, temp, flag;
for (i = 0; i < n; ++i) {
flag = 0;
for (j = i; j < n-1; ++j) {
if (array[j] > array[j+1]) {
temp = array[j];
array[j] = array[j+1];
array[j+1] = temp;
flag = 1;
}
}
if (flag == 0){
/* 一趟排序過(guò)程中沒(méi)有發(fā)生關(guān)鍵字交換
* 則證明序列有序闻妓，排序結(jié)束*/
return;
}
}
}
void print_array(int array[], int n){
for (int i = 0; i < n; ++i)
cout<<array[i]<<" ";
cout<<endl;
}
int main() {
int array[] = {1, 3, 8, 4, 6, 7};
print_array(array, 6);
BubbleSort(array, 6);
print_array(array, 6);
return 0;
}
復(fù)雜度分析：
1. 時(shí)間復(fù)雜度：
1）最壞情況：內(nèi)層循環(huán)每次都執(zhí)行， 故時(shí)間復(fù)雜度為O(n^2)
2）最好情況：原本就有序掠械，內(nèi)層循環(huán)不發(fā)生由缆，時(shí)間復(fù)雜度為O(n)
綜合來(lái)看注祖，時(shí)間復(fù)雜度為O(n^2).
2. 空間復(fù)雜度：
只需要一個(gè)temp， 故空間復(fù)雜度為O(1)均唉。
