反思

翻了一下 17 年写的那些排序代码，一脸茫然，似乎从来没有写过。一下子想不起快排的实现思路，想不起堆排序的细节，更不用说时空复杂度和适用场景。不由得吐槽当初是怎么学的这些东西，有什么意义。进一步想想，没能深入理解和扎实地记住这些点，最直接的原因之一是平时真的没有用到，环境没有需要你掌握它，有的只是调用一下封装精良的库。它变成了一个对很多程序员透明的东西。

某些角度来看它是好事，因为程序员可以“专注地干自己的事”，有些人能敏捷地调用库函数，高效率地“产出”，一边在想我是多么的有成就感，灵活地使用这些开箱即用的库或组件做成了一个“系统”，另一边在几年的不断重复中又深感厌倦迷茫。

社会总是呈现出它残酷的一面，一句”让程序员能专注地干自己的事情“，极大地提高了社会和行业整体的产出效率，对其有不同理解的人，也走上了不同的路。

回头想想，排序这种知识点不应该在程序员眼前透明化，它本是工作的基石之一，记得刚开始学编程，课堂上老师就反复演示如何用两个 for 循环实现冒泡，在实际工作中排序也是被提到最频繁的需求之一。

只要有列表的地方就有排序的需求，或简单或复杂，在搜索这种场景下，排序更是核心中的核心，而其实现难度也随着数据量和场景的变化，演变成完全不同层次的问题。也聚集了计算机领域大量的智慧和知识，大点的像 PageRank，小点的就是我等所学的快排、组合、堆等等小算法。

在反思完之前糟糕的学习方式后，接下来进入正题，复习一下这些基本小算法。

三大重要属性

软件工程最实际的目标之一就是：以最小的成本实现最高的效率。这也引导了排序算法的成长方向：

• 低时间复杂度
• 低空间复杂度

时间复杂度就引出了计算机中一个重要的概念，大 O 标记法，用来描述在数据量 (n) 增长时，算法所消耗时间的增长方向，这是一个定性的概念，一般会忽略常数、系数和低阶值。比如 O(1)，就描述算法不受数据量的增长影响，始终保持为常数，而 O(n)，则是随着数据量的增长线性增加。排序的一般过程是不断地进行比较和交换两个操作，涉及的底层操作就是数据访问和数据交换，访问和交换都少的算法，一般都比较快。

空间复杂度则是描述在排序过程中，额外消耗的内存空间的增长方向，与时间复杂度类似。当排序过程中的空间复杂度是 O(1) 时，这种排序算法也被称为原地排序，在对大规模数据排序时，原地排序是一个重要的选择指标。

而排序本身还有一个很重要的属性，就是排序稳定性。稳定性的含义是待排序序列中相同的值在排序完成之后，其原来的相对顺序是否保持不变，如果不变那就是稳定的，不然就是不稳定的。在简单的数字排序中，稳定性不重要，因为相同的数字之间并没有什么差别。但是在实际的排序场景中，我们的排序序列大多是一组对象，通过这些对象的某个属性值来进行排序，这时候稳定性就是一个不能忽视的点了。

稳定的排序算法可以帮助实现一些复杂的需求，比如订单排序，按照下单日期进行排序，日期相同的再按金额大小排序。实现方案可以是先按照金额大小为订单排一次序，然后再用稳定的排序算法按照日期排序，由于稳定的排序不改变相同值原有的顺序，所以第一次排序后时间相同的订单相对顺序在第二次排序后依然不变 (依然保持金额大的在前)。这样通过两次排序就实现了这个需求。

接下来就慢慢复习一下常见的排序小算法，并依次分析它们的时间复杂度、空间复杂度、稳定性。

比较交换

在被教育洗脑的过程中，冒泡是最先接触的算法，也是最简单的之一。它从头到尾不断比较相邻的元素大小，像冒泡一样把当次最大的值拱到数组的末尾，重复 n 次，就实现了排序。

func bubbling(a []int){
    var temp int; var sorted bool
    for i := 1; i < len(a); i++{  //外层
        sorted = true
        for j := 0; j < len(a) - i ; j++{ // 内层
            if a[j] > a[j+1]{ //交换，将前面的大值往后冒
                temp = a[j]; a[j] = a[j+1]; a[j+1] = temp; sorted = false
            }
        }
        if sorted {break}
    }
}

如上，外层执行 N-1 次，内层循环最多时执行 N-1 次，最少时执行 1 次，总次数大概如下：

N-1 + N-2 + ···+ 2 + 1  =>  (N^2-N)/2

去掉常数项，时间复杂度为 O(N^2) 。 空间消耗为 temp 变量的消耗，恒定，原地排序。 交换条件保证前面大于后面时才交换，可以保证稳定性。

冒泡排序的有序区间在数组尾部，每次冒泡过程就在往前扩张有序区间。冒泡的交换次数等于数组的逆序度，当数组已经有序时，它不会交换操作，其逆序度为零，当逆序度不为零时，它每一次交换操作会有三次赋值操作，这对应到上面提到的数据访问次数，这个指标是冒泡和插入性能差别的关键点，接下来看看插入排序。

插入排序的也有有序区间，默认为数组的第一个元素。插入排序就是遍历无序区间，将无序区间的元素插入到有序区间中合适的位置，它往后扩张有序区间。冒泡的有序区间能减少后面过程中的比较交换次数，当后面的数已经大于有序区间尾部的数时，当次比较就可以直接退出，插入排序对于有序的序列效率很高。

func insert(a []int){
    var temp , i, j int
    for i = 1; i < len(a); i++{ // 遍历无序区间
        temp = a[i]
        for j = i - 1; j>=0; j--{
            if a[j] <= temp { break } // 退出本次比较
            a[j + 1] = a[j] // 往后移动
        }
        a[j + 1] = temp // 将值插入合适的位置
    }
}

时间复杂度和冒泡一样，外层 N-1 次，内层循环最少 1 次，最多 N-1 次，大概为：

1 + 2 + 3 + ··· + N-1  

去掉常数项，时间复杂度为 O(N^2) 。 空间消耗恒定，原地排序。 后面小于前面才交换，稳定。

对比于冒泡，插入排序的循环消耗与其一致，移动的次数也等于逆序度，但是插入排序的性能要好于冒泡，大概是常数倍的差异。其原因上面做过铺垫，冒泡排序移动元素需要三次赋值，而插入排序只需要一次，差异主要产生于 cpu 读写数据上的消耗。

插入在对大规模数据排序时性能都相对低下，因为它只交换相邻的元素，元素也只能一位一位地从一端被移动到另一端。假设数组中最小的元素恰好在数组末尾，那么这个元素需要被移动 N-1 次才能到达正确的位置。而这些元素其实可以一次性被移动到正确的位置，或者跳跃式地被移动到正确的位置，这样它的移动次数会大大缩减。这种优化后的排序就是希尔排序。

希尔排序将整个数组在逻辑上分为了多个小数组，排序过程中让这些小数组中的元素变得相对有序，会进行多轮的跳跃式地比较和交换，也就是有间距地进行插入排序 (原本间距是 1)。每轮排序后这个间距会递减，当间距减到 1 时 (最后一轮)，就和纯正的插入排序一样了。但这时，数组已经呈现出相对有序，以较少的交换就可以让数组完全有序。

通过图片来形象地理解这个过程，图中的 gap 就是每次跳跃的间距。图片来源

func shell(a []int){
    size := len(a)
    gap := size/2 // 默认为数组的一半。gap的最优选择策略比较复杂
    var i, j, temp int
    for gap > 0{
        for i = gap; i < size; i ++{ // 这里面本质是插入排序，只是gap在变化
            temp = a[i]
            for j = i; j >= gap; j -= gap{
                if temp >= a[j - gap] {break}
                a[j] = a[j - gap]
            }
            a[j] = temp
        }
        gap = gap/2 // gap等于1时，这就是一个纯正的插入排序
    }
}

希尔排序的性能描述非常复杂，被认为是第一个时间复杂度小于 O(N^2) 的排序算法，水比较深，就不在这里瞎扯了。也可以看出其也是原地排序。

而对于稳定性来讲，希尔排序会将元素分为不同的组，让这些组中的元素变得相对有序，在分组中实际进行的是插入排序，这是稳定的。但是每一轮排序后，会重新进行分组，值相同的元素可能会被分到不同的组，而组于组之间各自的排序会打乱原有的稳定性，所以，希尔排序是不稳定的。

分而治之

常见的使用分治思想实现的排序有归并排序和快速排序两种，都可以使用递归来简洁地实现。

归并排序的思路是将一个数组组拆成两个小数组，分别对小数组进行排序，然后将这两个有序的小数组合并成一个数组，这样便实现了排序。有三个核心步骤：

• 一分为二
• 各自排序
• 合二为一

合并 (图片来源)：

拆分和合并都可以在递归中进行，简单的实现思路是，每次将数组拆成两个独立的小数组，然后将其各自排序，再将两个小数组合并成第三个数组，用这个数组去替换原来的数组，这样便实现了排序。这样虽然实现上较为简单，但是空间复杂度太高，在大规模排序的场景下难以接受，所以得向原地排序的方向走，不额外使用新的空间。原地归并排序实现比较复杂，这里简要阐述原理，就使用一个额外的数组，实现自顶向下空间复杂度为 O(N) 的排序。

func sort(a []int, start int, end int, temp []int){
    if start >= end {return}
    middle := start + (end - start)/2 // 防止int溢出

    sort(a, start, middle, temp)
    sort(a, middle+1, end, temp)
    merge(a, start, middle, end, temp)
}

func merge(a []int, start int, middle int, end int, temp []int){
    // 做备份
    for i := start; i <= end; i++{
        temp[i] = a[i]
    }

    left := start;
    right := middle + 1
    index := start
    //merge
    for(left <= middle || right <= end){
        if left > middle {
            a[index] = temp[right]; right++
        }else if right > end {
            a[index] = temp[left];  left++
        }else if temp[left] > temp[right] {
          a[index] = temp[right];  right++
        }else{
            a[index] = temp[left];  left++
        }
        index++
    }
}

sort(a, 0, len(a) -1, make([]int, len(a)))

归并排序的时间复杂度分析稍微有点麻烦，可以大致认为，总消耗=排序上半个数组的消耗 + 排序下半个数组的消耗 + 合并两个数组的消耗

Cost(N) = 2*Cost(N/2) + Merge(N/2, N/2)   // Merge(N/2, N/2) 为 O(N)

N 大于 1 时，等式的右半部分的每一块，都为各个递归小任务的总和：

Cost(N/2) = 2*Cost(N/4)  + Merge(N/4, N/4)
Merge(N/2, N/2) =2* Merge(N/4, N/4)
···

Merge(N/2, N/2)时间复杂度为 O(N)，进一步推导 (假设 N 为 2 的倍数)：

Cost(N) = 2*Cost(N/2) + O(N)
        = 4*Cost(N/4) + O(N) + O(N) //  2*Merge(N/4, N/4) = Merge(N/2, N/2) = O(N)
        = 2^k*Cost(N/2^k)) + k*O(N)

由归并排序的退出条件可以知道 k = log(N)，代入上面的公式，可以得到：

Cost(N) = 2^log(N)*Cost(N/2^log(N)) + log(N)*O(N)
        = N*O(1) + log(N)*O(N)         //  N/2^logN = 1 其操作是常数级别消耗
        = O(N) + log(N)*O(N)
        = O(N*log(N)) // 忽略常数

从推导可以看出，归并排序的时间复杂度是N*log(N)，其时间复杂度很稳定，和输入序列的有序状态关系不大，不管是否有序都会走分分合合的流程，所以常规的优化措施中会先检测数组是否已经有序，有序就停止归并。

归并排序在强大之处不只是在于其n*log(n)的时间复杂度，还在于其因为归并模型而表现出的强大的灵活性：

• 可以用复杂的原地 Merge 方案 (in-place algorithm)，来降低空间复杂度
• 可以在过程中用其他算法来排序小数组，例如插入排序，提升排序性能
• 可以更改实现的细节，让排序过程在多线程、多机器上并行执行

上面的实现其空间复杂度为 O(N)，也有复杂的原地方案，可达到 O(1)。同时上面的代码示例是从头开始归并，可以保证稳定，但不同的 Merge 策略会影响其稳定性，稳定性需视情况而定。

另一种依靠分治思想的排序就是快速排序了，快速排序也会数组分为两部分，分别独立排序。归并是将各自有序的数据合并以达成全局有序，而快排是让各数组各自有序后，整体也就有序了。归并在递归调用之后处理数组，而快排是在处理之后才递归调用。

实现细节是，快排会在数组中找一个基准点，一般是随机规定，比如当前数组的第一个元素。找到基准点之后，会遍历整个数组，将大于基准点的元素交换到数组右边，小于的交换到数组左边，基准点会被放到中间。整个过程完毕后，数组被分为三个部分，左边小于基准点、基准点、右边大于基准点。然后递归地对基准点左右两边的子数组进行和前面一样的操作，整个过程完毕后，数组有序。

func Sort(array []int, l int, r int){
    if l >= r  {return}  // 数组只有一个元素，有序
    point := Partition(array, l, r) //将数组分为三部分，返回基准点
    Sort(array, l, point) // 重复操作基准点左边的数组
    Sort(array, point + 1, r) // 右边的数组
}

func Partition(array []int, l int, r int) int{
    benchmark := array[l] //将第一位作为基准点
    left := l; right := r
    var temp int
    for(left != right){
        for(left < right){
            if array[left] > benchmark {break}
            left += 1
        }
        for(right > left){
            if array[right] < benchmark {break}
            right -= 1
        }
        temp = array[left]; array[left] = array[right]; array[right] = temp //交换
    }
    partition := left - 1 //左右分区点
    temp = array[l]; array[l] = array[partition]; array[partition] = temp // 交换
    return partition
}
Sort(a, 0 , len(a) - 1) // 调用

快排会不断地分区交换，相同的元素的稳定性很容易被打破，特别是相同元素中有作为基准点的，它是不稳定的排序算法。可以看出 Partition 消耗的空间是恒定的，快排是原地排序算法。

快排的递归模型和归并排序一致，当每次 Partition 都恰好把数组分为两个一样大小的子数组时，快排的时间复杂度达到最优，由于Partition(N)每次会遍历一次数组，其时间复杂度为O(N)，所以求解方式和上面的归并排序一致。而快排每次不可能都将数组均匀一分为二，当极端情况下，例如对下面的序列：

1, 2, 4, 5, 7, 9

进行快排，且每次以数组最后的元素为基准，那么每次分区后的数组规模会极端不均匀，一个是 N-1，一个为 1。此时需要接近 N 次 Partition，每次的扫描次数分别相加为：

N + N-1 + N-2 + N-3 + ··· + 2 + 1 = N + N*(N-1)/2

在这种极端情况下，也就意味着会退化到 O(N^2)，不过这个几率计较小，而且快排会用相对巧妙地 Partition 策略来避开这种情况，其优化的空间和策略非常多，可以让快排的时间复杂度维持在O(N*log(N))。

更加细致的推导可以通过递归树来实现，上面的理想情况，每次 Partition 都把数组均匀地分为两部分，这和归并一样，这样出来的递归树是一颗满二叉树：

对于树的求解和上面归并的求解方式一致。但快排毕竟不可能每次都均匀切分，得考虑其常规的情况。常规的方案是假设每次 Partition 切分出的两个数组大小为 9 比 1，推导公式也变化成：

Cost(n) = Cost(n/10) + Cost(n*9/10) + O(n)

递归树展开为： 这不是一颗满二叉树了，右边的深度会比左边的深度要大。我们知道快排的退出条件是子数组的大小为 1，也就是说最底部的叶子节点处理的数量是 1，那么上图树左边的深度就为log10(n)(10 为底)，右边则是log10/9(n)(10/9 为底)，而每一层的消耗都落在了 Partition，每层的总消耗都相当于遍历一次数组，时间复杂度为 O(n)，所以总的时间复杂度：

n*log10(n) < Cost(n) < n*log10/9(n)

根据时间复杂度定性的思想，底数和 n 没有关联，且是常数则忽略底数，上面的时间复杂度就是： n*log(n) 。由于这个时间复杂度，快排和并归常用来处理大规模的数据，而并归由于空间复杂度的原因，没有快排使用得普遍。

优先队列

优先队列是一种数据类型的抽象表达，它定义了一组抽象接口，这些接口可以对应多种实际的代码实现。这些实现按照优先级来操作数据。对于排序来讲，很多时候我们只需要在一组数据中找到最大的部分数据，例如 Top10 这种需求，它不关心剩下的那些数据的有序情况，所以不需要数据整体有序，对应排序的具体实现就是堆排序。

堆排序是在堆中实现的排序算法，堆是一种特殊的树，有两个特性：

• 是完全二叉树，除了最后一层，其他层都是满的，没有空闲
• 堆中的每一个节点的值都必须大于 (或小于) 等于其子树中每个节点的值

上图 a 就是一个堆，每个节点的值都大于其子节点，也称为大顶堆。从 b 图中可以观察到这个大顶堆其实可以用一个数组来表达，不需要用标准的二叉树，这节约了大量的空间，也对排序操作很友好。

对于这个数组，一般其下标为 0 的地方都不存放数据，这样做是为了方便地用公式表达节点间的父子关系。这样下标为 i 的元素，其左子节点的下标为2*i，右子节点的下标为2*i + 1。另一个原因是在某些实现下下标 0 的位置可以用作哨兵节点 (特殊标志，例如数组已经有序)。

如果要使用下标为 0 的节点的话，下标为 i 的节点，其左子节点的下标为2*i + 1，右子节点则为2*i + 2，本质没什么区别，为了简单起见，我们就用后面这种方式来表达节点关系。

要进行堆排序的话，我们需要做两个操作：

• 将待排序数组组织成上述的堆 (堆化)
• 用堆排序算法进行排序操作

堆化，从最底层的非叶子节点 (有子节点) 开始往上依次堆化：

func build_heaping(a []int){
    for i := (len(a) - 2)/2; i >= 0 ; i--{ // 从底开始往上堆化
        heaping(a, len(a), i)
    }
}

func heaping(a []int, n int, i int){
    var left, right, temp, max_pos int
    for true{
        left = 2*i + 1; right = 2*i + 2
        max_pos = i
        if left < n && right >= n{ //右子树不存在
            if a[left] > a[max_pos] {max_pos = left}
        }

        if left < n && right < n{
            if a[left] > a[right] && a[left] > a[max_pos] {max_pos = left}
            if a[right] > a[left] && a[right] > a[max_pos] {max_pos = right}
        }

        if max_pos == i { break} // 节点已经大于了所有字节点，退出
        temp = a[max_pos]; a[max_pos] = a[i]; a[i] = temp
        i = max_pos  //每次交换后，子节点需要重新堆化。 从上往下走
    }
}

堆化的代码如上，其中难点在于，当某个值较大的节点和其父节点交换值之后，这个节点需要重新堆化，因为从父节点换下来的值可能比较小，要把这个值继续往下换，直到节点大于其左右节点为止 (或到底了)。堆化后的数组，可以接受新插入的值，并能在 log(n) 的时间复杂度内保持堆有序。

排序的过程其实就是不断地执行堆化，当第一次堆化完成之后，堆顶 (下标为 0) 的元素就是当前数组中最大的值。我们将这个值交换到数组最后，也就是将数组第一个值和数组最后一个值交换。

交换的结果是，堆顶的元素不是最大的值了，需要重新堆化。这时候堆化时，就不让数组最后一个值参与进来，让剩下的 n-1 个元素参加堆化，当堆化完毕后，又将第一个元素换到当前数组末尾，然后又继续堆化，当数组长度变成 1 时，堆排序就全部完成了。本质上就是每次堆化，都选择出当前的最大值，然后将这个最大值移除出堆，重复 N-1 次，数组就变成完全有序。

当要求 Top10 时，就重复上述过程 10 次，然后取出数组最后 10 个元素，这 10 个元素就是 Top10，避免了将数组完全有序化。

func sort(a []int){
    var temp int
    build_heaping(a)
    for j := len(a) -1; j > 0; j--{
        temp = a[0]; a[0] = a[j]; a[j] = temp
        heaping(a, j, 0)
    }
}

可以看出堆排序是原地排序，其消耗的临时空间很稳定。同时在排序的过程中，会将堆顶的元素和最后一个元素互换，这会导致不稳定，所以堆排序是不稳定的。

接下来推导一下时间复杂度，当在重建堆时，将堆顶元素下沉到合适的位置时，因为堆具备树的性质，将该节点沉到合适的位置最多需要log(n)次操作 (沉到叶子节点)，而完全排序这个数组约需要 1 次建堆和n次重建堆，n 次重建堆时间复杂度为 O(n*log(n)) ，第一次建堆需要遍历 n/2 个节点，每个节点建堆的时间复杂度大概为 log(n)，所以第一次建堆的时间复杂度也为： O(n*log(n))，两者相加忽略常数可以得到，整个过程时间复杂度为：O(n*log(n)) 。

堆排序一般要比快排稍慢，因为堆排序在调整顺序时是跳着访问元素，而快排是接近顺序访问，这对 cpu 缓存更友好。同时，据统计快排比堆排序有更少的交换次数。

可视化

http://jsdo.it/norahiko/oxIy/fullscreen

TL;DR

这些小算法并不简单···尤其是涉及到到它们的优化和改进时。越写越自知水平有限，希望本文能被勉强看懂。