排序：冒泡排序算法分析

1.交换排序

基于“交换”的排序︰
根据序列中两个元素关键字的比较结果来对换这两个记录在序列中的位置。

交换排序包括冒泡排序和快速排序。

2.冒泡排序

1.算法原理

1. 从后往前(或从前往后)两两比较相邻元素的值，
2. 若为逆序(即$A[i-1]>A[i]$) ，则交换它们，直到序列比较完。
3. 每一趟排序都可以使一个元素的移动到最终位置，已经确定最终位置的元素在之后的处理中无需再对比。
4. 如果某一趟排序过程中未发生“交换”，则算法可提前结束。
5. 称这样过程为“一趟”冒泡排序。总共需进行n-1趟冒泡。

2.代码实现

从后往前冒，每一次排头得到当前较小值。

//交换
void swap(int &a,int &b){
    int temp = a;
    a = b;
    b = temp;
}
//冒泡排序
void Bubblesort(int A[ ] ,int n){
    for(int i=0; i<n-1 ; i++){
        bool flag=false;//表示本趟冒泡是否发生交换的标志
        for(int j=n-1;j>i;j--)//一趟冒泡过程
            if(A[j-1]>A[j]) {//若为逆序
                swap(A[j - 1], A[j]);//交换
                flag = true;
            }
        if(flag==false)
            return;//本趟遍历后没有发生交换，说明表已经有席t
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

只有$A[j-1]>A[j]$时才交换，因此算法是稳定的

3.算法性能分析

1.空间复杂度：$O(1)$

2.时间复杂度

• 最好情况(有序)：
  比较次数=n-1;交换次数=0；
  最好时间复杂度=$O(n)$
• 最坏情况(逆序)：
  比较次数=$(n-1)+(n-2)+...+1=\frac{n(n-1)}{2}$=交换次数;
  最坏时间复杂度=$O(n^2)$

平均时间复杂度=$O(n^2)$

4.适用性

顺序表、链表都可以。