06 Jun 2017

冒泡排序

冒泡排序，顾名思义就是像冒泡一样进行排序，那么是怎么个冒泡法呢？

举个例子说明一下，比如有一个数组：[3 2 1 0]，需要将该数组进行升序排序，即排序成：[0 1 2 3]。

冒泡排序是这样进行排序的，首先将第一个元素和第二个元素进行比较，如果第一个元素比第二个元素大，那么将这两个元素交换位置，比如这里的第一个元素是3，第二个元素是2，那么第一次排序后，数组变成：[2 3 1 0]，3往后移动了一位，然后重复刚刚的步骤，将第二个元素和第三也进行比较，数组变成：[2 1 3 0]，再将第三个元素和最后一个元素重复之前的比较，数组变成：[2 1 0 3]。

发现了吗？最大的元素3像一个泡泡一样，慢慢“冒”出来了，数组变化过程如下：

[3 2 1 0] -> [2 3 1 0] -> [2 1 3 0] -> [2 1 0 3]

找出最大的元素后，重复刚刚的步骤，继续找第二大的元素，数组变化过程如下：

[2 1 0 3] -> [1 2 0 3] -> [1 0 2 3]

第二大的元素2，也慢慢“冒”出，继续找第三大元素，数组变化过程如下：

[1 0 2 3] -> [0 1 2 3]

第三大元素1也“冒”出来了，到此，排序结束，这就是冒泡排序的由来。当然，冒泡排序还有好几种改进版本，就不深入介绍了。

写这篇文章的目的只有一个：再简单的算法，不自己动手试试，是不会明白的。你别不信，随便问问你身边的程序员，一说快速排序都知道，能一次性写对的，估计真的没几个。

附上go实现的冒泡排序代码：

package main

import "fmt"

func main() {
    array := []int{3, 2, 1, 0}
    fmt.Printf("      array: %v\n", array)
    bubbleSort(array)
    fmt.Printf("bubble sort: %v\n", array)
}

func bubbleSort(array []int) {
    size := len(array)
    for i := 0; i < size-1; i++ {
        for j := 0; j < size-1-i; j++ {
            if array[j] > array[j+1] {
                array[j], array[j+1] = array[j+1], array[j]
            }
        }
    }
}

运行结果：

array: [3 2 1 0]
bubble sort: [0 1 2 3]

本次荐书：人类简史：从动物到上帝

LEo at 22:26