冒泡排序

要给大家介绍的是基于选择的排序算法，常见基于选择的排序算法有冒泡排序、插入排序、选择排序、归并排序和快速排序，我们在选择排序算法的时候，通常会根据以下几个维度来考虑：

1. 时间复杂度
2. 空间复杂度（对内存空间的消耗）
3. 算法的稳定性（如果待排序的序列中存在值相等的元素，经过排序之后，相等元素之间原有的先后顺序不变）

我们首先从冒泡排序开始。

实现原理

冒泡排序只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个元素进行比较，看是否满足大小关系要求，如果不满足就让它俩互换。一次冒泡会让至少一个元素移动到它应该在的位置，重复 n 次，就完成了 n 个数据的排序工作。
冒泡排序是一种交换排序，核心是冒泡，把数组中最小的那个往上冒，冒的过程就是和他相邻的元素交换。
重复走访要排序的数列，通过两两比较相邻记录的排序码。排序过程中每次从后往前冒一个最小值，且每次能确定一个数在序列中的最终位置。若发生逆序，则交换；有俩种方式进行冒泡，一种是先把小的冒泡到前边去，另一种是把大的元素冒泡到后边。
光看定义有点抽象，我们用图来演示，假设待排序数字是 4、5、6、3、2、1，第一次排序的流程是这样的：

经过 n 次冒泡，最终完成排序（所谓冒泡，以升序来看，就是每次把待排序序列中的最大值插到已排序序列的最前面，这个过程就像冒泡一样）：

动图演示

示例代码

通过两层循环控制：

• 第一个循环（外循环），负责把需要冒泡的那个数字排除在外；
• 第二个循环（内循环），负责两两比较交换；

重要的是理解冒泡排序的原理，懂了原理就是把这个排序过程翻译成代码而已，以下是 Go 代码实现的冒泡排序：

package main

import "fmt"

func bubbleSort(nums []int) []int {
    if len(nums) <= 1 {
        return nums
    }

    // 冒泡排序核心实现代码
    for i := 0; i < len(nums); i++ {
        flag := false
        for j := 0; j < len(nums) - i - 1; j++ {
            if nums[j] > nums[j+1] {
                nums[j], nums[j+1] = nums[j+1], nums[j]
                flag = true
            }
        }
        if !flag {
            break
        }
    }

    return nums
}

func main() {
    nums := []int{4, 5, 6, 7, 8, 3, 2, 1}
    nums = bubbleSort(nums)
    fmt.Println(nums)
}

这里我们使用切片类型来存储待排序数据序列，并且可以看到，我们对冒泡排序有个小小的优化，就是当某一次遍历的时候发现没有需要交换的元素，则认为整个序列已经排序完成。

性能分析

最后我们来看下冒泡排序的性能和稳定性：

1. 时间复杂度： $O(n^2)$
2. 空间复杂度：只涉及相邻元素的交换，是原地排序算法
3. 算法稳定性：元素相等不会交换，是稳定的排序算法

时间复杂度是 $O(n^2)$，看起来性能并不是很好，所以我们在实践中基本不会选用冒泡算法。