冒泡排序，是一种交换类的排序，通过一系列交换动作完成。在排序过程中，第一个关键字和第二个比较，若第一个大，则交换，否则不交换；然后第二个与第三个比较，进行之前类似动作，知道最大的关键字到了序列的最后，则一趟冒泡排序完成。无序序列元素减一，有序序列元素加一。经过多次排序，然后无序序列变为有序序列。
算法结束条件 = $\color{blue}{在一趟排序过程中没有发生关键字交换}$。
下边是算法的具体实现 =
#include <iostream>
#include <stdio.h>
#include <cstdio>
#include <vector>
#include <algorithm>
#include "dbg.h"
using namespace std;
void bubbleSort(int R[], int len)
{
int flag; // 交换标志
for (int i = len - 1; i >= 1; i--) // 无序序列范围
{
flag = 0;
for (int j = 1; j <= i; j++) // i不断减小，无序序列元素不断减少，i之后都是有序序列元素
{
if (R[j-1] > R[j]) // 前一个关键字大于后一个，则交换
{
int temp = R[j];
R[j] = R[j-1];
R[j-1] = temp;
// 若发生交换，将falg置为1
flag = 1;
}
}
if (flag == 0) // 一趟排序中没有发生交换，则有序，算法结束。
return;
}
}
int main(int argc, char *argv[])
{
int R[] = {1, 3, 2, 18, 3, 28, 23, 38, 7, 8};
cout << "Before sorting = " << endl;
dbg(R);
int len = sizeof(R) / sizeof(R[0]);
cout << "After sorting = " << endl;
bubbleSort(R, len);
dbg(R);
return 0;
}
运行结果 =
时间复杂度
- 最坏情况：序列逆序, 为$\color{blue}{O(n^2)}$。此时内外循环都要执行。
- 最好情况：序列有序，为$\color{blue}{O(n)}$。此时if条件始终不成立，内层循环执行n-1次后算法结束。
空间复杂度$\color{blue}{O(1)}$ = 交换时使用的辅助变量temp，故为$O(1)$.