冒泡排序

基本思想

每次都操作两个相邻的数据.每次冒泡操作都对相邻的两个数据进行比较,看是否满足大小关系要求,如果不满足,就进行互换。每次冒泡都会冒出一个最小/大值，并移动到它应该在的位置.重复n次,就完成了对n个数据的排序工作.

排序逻辑图

这里在详细的写一下第一次排序的过程：

按照以上逻辑的代码实现

算法实现

int *bubble_sort(int *a, int length) {

    for (int i = 0; i < length; i++) {
        for (int j = 1; j < length-i; j++) {
            if (a[j - 1] > a[j]) {
                int temp = a[j - 1];
                a[j - 1] = a[j];
                a[j] = temp;
            }
        }
        // print(a, length);
    }
    return a;
}

这种实现，在这种情景下，就会浪费时间。

如果原始数组为:

[5,0,1,2,3,4]

排序过程如下:

可以发现,在完成第一趟排序的时候，实际上已经是正确的排序结果了.我们可以采用下面的方式进行优化

int* bubble_sort(int *a, int length){

    for (int i = 0; i < length; i++) {
        int flag = 0;
        for (int j = 1; j < length - i; j++) {
            if (a[j - 1] > a[j]) {
                int temp = a[j - 1];
                a[j - 1] = a[j];
                a[j] = temp;
                flag = 1;
            }
        }
        if (!flag) {
            break;
        }
        //print(a, length);
    }
    return a;
}

从上面的代码可以看出:

• 冒泡排序是基于比较,交换的排序算法。
• 冒泡排序使用的空间复杂度为$O(1)$,是一个原地排序算法。
• 以上代码实现的冒泡算法是稳定的排序算法. if(a[i]<=a[j])就是一个不稳定的排序算法了.
• 冒泡算法最好情况下的时间复杂度是$O(n)$,最坏情况下的时间复杂度是$O(n^2)$. 那平均情况下的时间复杂度怎么计算呢?

计算平均情况下的时间复杂度

这里，我们引入三个概念

• 有序元素对: 如果 i<j ,并且 a[i]<a[j],那么这个一对儿数就是有序的。
• 逆序元素对: 如果 i<j ,并且 a[i]>a[j],那么这个一对儿数就是逆序的。
• 有序度: 数组中具有有序关系的元素对的个数.
• 满有序度: 完全有序的数列。

其中 满有序度 = 有序度 + 逆序度。

举个例子:

[4,5,6,3,2,1]

有序度为3,也称为 原始有序度, 分别为: (4,5) (4,6) (5,6)

满有序度为 $\frac {n*(n-1)}{2}=15$

冒泡排序中包含两个操作原子,比较和交换.没交换一次，有序度就会加1. 所以，交换次数，就是逆有序度。 那么，逆有序度 = 满有序度 - 初始有序度. 也就是: 15 - 3 = 12. 需要进行12次操作。

平均情况下，要进行$\frac {n*(n-1)}{4}$次操作. 比较操作肯定要比交换操作多，而最坏情况下的时间复杂度就是 $O(n^2)$, 所以平均情况下的时间复杂度就是 $O(n^2)$

最后

期望与你一起遇见更好的自己