Bubble Sort

冒泡排序，是一种交换类的排序，通过一系列交换动作完成。在排序过程中，第一个关键字和第二个比较，若第一个大，则交换，否则不交换；然后第二个与第三个比较，进行之前类似动作，知道最大的关键字到了序列的最后，则一趟冒泡排序完成。无序序列元素减一，有序序列元素加一。经过多次排序，然后无序序列变为有序序列。

算法结束条件: $\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;
}

运行结果:

时间复杂度

1. 最坏情况：序列逆序, 为$\color{blue}{O(n^2)}$。此时内外循环都要执行。
2. 最好情况：序列有序，为$\color{blue}{O(n)}$。此时if条件始终不成立，内层循环执行n-1次后算法结束。

空间复杂度$\color{blue}{O(1)}$: 交换时使用的辅助变量temp，故为$O(1)$.