【小算法】冒泡排序

冒泡排序是大多学人学到的第一个排序，教科书上在众多的排序算法中选择它作为示例，我想还是因为它够简单，易于理解吧。

假设有下面一组数据，需要从小到大升序排列。

冒泡排序的算法是

1. 从左到右，依次比较相邻两个位置的数据，如果左边的数值较大，就交换它们，这样在单轮操作中，最大的数会交换到最右边。
2. 重复多轮操作，重复的次数和数组的长度相同。
3. 排序完成。

冒泡排序的过核心思想就是 交换。

通过交换，可以保证每一轮操作，将最大的数挪到最右边，这有点像池塘里面水泡从淤泥中浮出水面的过程，所以它叫冒泡排序。

以图例来说明就非常简单了。

假设我们要对数组[7 1 12 6] 排序 图例示意：

我们先看每一轮的操作

在这里插入图片描述

用红框标出每次两两交换的数据，可以看到比较到最后，12 排到了最上面的位置。

我们再看整个过程：

在这里插入图片描述

每一次都有数据冒泡到最右边，最后一次操作，比较时已经不再需要做交换了。

Python 代码演示：

def bubble_sort(srcArr):

    size = len(srcArr)

    for i in range(size):
        for j in range (size - i - 1):
            if srcArr[j] > srcArr[j+1]:
                srcArr[j] += srcArr[j+1]
                srcArr[j+1] = srcArr[j] - srcArr[j+1]
                srcArr[j] -= srcArr[j+1]


    return srcArr



if __name__ == "__main__":

    arr = [3,2,8,4,1,6,5]
    print("=======================")
    print(arr)

    result = bubble_sort(arr)

    print("=======================")
    print(result)

运行结果如下：

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

可以看到，排序结果正确。

也许有同学会问，j 的取值为什么是 size - i - 1 呢？

每次冒泡排序后，因为最右边的数字是排序好的，所以每一轮的操作实际上会变少。

比如第二次排序时，只比较数组前面 N-1 个数字就好了，第三次排序只比较前面 N-2 个数字就好了。

至于为什么减去 1 呢，这是因为防止数组索引溢出，每次用 j 做下标，与 j+1 的下标比较，要确定 j+1 的索引不会超出范围。

另外，我还使用了不借助第三个变量，交换两个变量的技巧。

举个例子：

你有 3 个苹果，小李有 4 个苹果。

加起来有 7 个苹果。

现在 7 个苹果减去你拥有的苹果数量为 4，把这 4 个给你。

7 个苹果再减去你当前拥有的 4 个再给小李，那么小李就 3 个了。

简单一轮操作，你们就完成了交换。

似乎有些不公平的意味在里面。

时间复杂度

冒泡排序的时间复杂度是 O(n2)O(n^2)O(n2)