冒泡排序是最笨的排序算法，得名于它的排序过程，即（以升序排序为例）：给定一个数组，比较相邻数值，若左侧数大于右侧，则交换两者；假定有N个数，则一趟排序需要比较N-1次，然后最大的数值在一轮比较之后被交换至最右侧。类似气泡往上冒一样，最大的数值依次往右边移动，故称为冒泡排序。

冒泡排序特点

冒泡排序最差的时间复杂度为O(n²),最好为O(n)，属于稳定排序，空间复杂度为O(1)。

原始冒泡排序

按照冒泡的基本思路实现的代码（Go版本）如下：

func MainFunc (args []int) {
    swapTimes := len(args) - 1
    exchange, compare := 0,0
    for swapTimes > 0 {
        bound := swapTimes
        for i := 0; i < bound; i++ {
            compare++
            if args[i] > args[i + 1] {
                exchange++
                args[i], args[i + 1] = args[i + 1], args[i]
            }
        }
        swapTimes--
    }
    fmt.Println("compare:", compare, "exchange: " , exchange)
    fmt.Println(args)
}

优化冒泡排序

对于基本有序的数组进行排序，其实可以做一下优化。当某次比较过程中发现并没有数据交换，那则表明该段数据已经有序，仅需记录该段数据的起始下标，对下标之前的数据进行排序即可，代码（Go版本）如下：

func MainFuncQuickEnd(args []int) {
    flag := len(args) - 1
    exchange, compare := 0,0
    for flag > 0 {
        limit := flag
        preExchange := exchange
        for i := 0; i < limit; i++ {
            compare++
            if args[i] > args[i + 1] {
                exchange++
                flag = i
                args[i], args[i + 1] = args[i + 1], args[i]
            }
        }
        if preExchange == exchange {
            break
        }
    }
    fmt.Println("compare:", compare, "exchange: " , exchange)
    fmt.Println(args)
}

优化前后对比

对于基本有序的数组，如{2,1,5,4,0,6,7,8,9}，进行排序，优化前需要比较36次，交换6次；优化后需要比较14次，交换6次。对于完全乱序的数组，两者差别并不是很大。