(64)王道数据结构-冒泡排序

基本概念

根据序列中两个元素关键字的比较结果来对换这两个记录在序列中的位置。

冒泡排序基本思想是：假设待排序表长为n，从后往前(或从前往后) 两两比较相邻元素的值，若为逆序(即A[i-1]>A[i])，则交换它们，直到序列比较完。

代码逻辑

//交换
void swap(int &a, int &b) {
    int temp = a;
    a = b;
    b = temp;
}
//冒泡排序
void BubbleSort(ElemType A[], int n) {
    //用冒泡排序法将序列A中的元素按从小到大排序
    for(i=0; i<n-1; i++) {
        flag = false; //表示本趟冒泡是否发生交换标志
        for(j=n-1; j>i; j--) {
            if(A[j-1].key>A[j].key) { //若为逆序
                swap(A[j-1], A[j]); //交换
                flag=true;
            }
        }   
        if(flag==false) {
            return; //本趟遍历后没有发生交换，说明表已经有序
        }
    }
}

性能分析

空间复杂度

空间效率：仅使用了常数个辅助单元，因而空间复杂度为O(1)

时间复杂度

最好时间复杂度: O(n)
最坏时间复杂度: O(n^2)
平均时间复杂度: O(n^2)

稳定性

由于i>j且A[i].key=A[j].key时，不会交换两个元素，因此冒泡排序是一种稳定的排序方法。