交换排序

交换排序的特点是每经过一趟排序，都至少确定一个元素的位置。典型的算法是冒泡排序和快速排序。冒泡排序经过一趟排序将会确定一个最大或最小的元素，而快速排序每一趟都至少会确定 pivot 的位置。这篇笔记记录了冒泡排序算法，在下一篇文章中记录了快速排序算法。

冒泡排序

算法思想

将序列中的元素两两比较，若顺序为逆序则交换位置。同时设置一个 flag 作为标识符来记录一趟排序中是否发生了交换行为，如果没有发生交换说明序列是有序的。

C语言实现（增序）

BubbleSort

void BubbleSort(int* a, int n){
    for(int i=0;i<n-1;i++){
        int flag = 0;
        for(int j=0;j<n-i-1;j++){
            if(a[j]>a[j+1]){
                flag = 1;
                int temp = a[j];
                a[j] = a[j+1];
                a[j+1] = temp;
            }
        }
        if(flag == 0)
            break;
    }
}

时间复杂度

平均情况	最坏情况	最好情况
$O(n^2)$	$O(n^2)$	$O(n)$

最好情况下，序列已经是有序的，只需要比较一趟即可，比较次数为 n-1，此时的算法复杂度为$O(n)$ 。最坏情况是序列为逆序的情况，比较次数为 $n(n-1)/2$ ，每一次比较需要 3 次交换，交换次数为$3n(n-1)/2$，此时的算法复杂度为$O(n^2)$。平均时间复杂度也为$O(n^2)$。

空间复杂度

$O(1)$ 。

稳定性

稳定。