冒泡排序(BubbleSort)
应该是最基础的一个排序方法啦，大一老师就讲过的，所以在我脑海中也是最熟的一个排序算法了.
冒泡排序顾名思义，在每躺冒泡中，大的关键字像石头一样“沉底”，小的关键字像气泡一样逐渐向上“浮动”，最终使得整个序列有序（这个概念解释好苍白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){
/* 一趟排序过程中没有发生关键字交换
* 则证明序列有序，排序结束*/
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;
}
复杂度分析：
1. 时间复杂度：
1）最坏情况：内层循环每次都执行， 故时间复杂度为O(n^2)
2）最好情况：原本就有序，内层循环不发生，时间复杂度为O(n)
综合来看，时间复杂度为O(n^2).
2. 空间复杂度：
只需要一个temp， 故空间复杂度为O(1)。
