1秒记住快速排序！

这几天在鼓捣算法动画视频，发现做动画比写算法题解有意思，因为每一行代码都能用动画显示出来，对于整个运行的流程更加直观，甚至能够看到大脑中没考虑到的细节。

上一篇文章我做了单调栈的动画，这一篇还是做一个稍微简单点的动画：快速排序。

快速排序

快速排序在我印象里面比较不好记住，特别是以前看算法导论的时候，要花比较长的时间去理解逻辑，实现的时候还要考虑边界问题，容易做错。然而这一次制作动画视频的过程中，发现自己能够非常轻松的手写快速排序，于是才能总结出1秒记住快速排序的方法。下面让我们一起来看看快速排序吧。

快速排序时间复杂度是，最差情况下退化到，一般情况下还是很快的。算法基本结构是分治算法，如下代码：

void quick_sort(int arr[], int low, int high)
{
    if (low < high) {
        int anchor = partition(arr, low, high);
        quick_sort(arr, low, anchor - 1);
        quick_sort(arr, anchor + 1, high);
    }
}

这段代码的意思是将区间[low, high]分成3部分，一个是锚点，一个是左区间，一个是右区间，对于左右区间，继续调用函数进行处理。每次调用都会把锚点位置空出来，像被镂空了一样。

这段代码没有记忆成本，只要能够理解肯定不需要死记硬背，所以记忆成本为0。

接下来看记忆成本为1秒的partition函数。

int partition(int arr[], int low, int high)
{
    int anchor = arr[high];
    int i = low - 1;

    for (int j = low; j <= high - 1; j++) {
        if (arr[j] <= anchor) {
            // 永恒经典，一次遍历搞定绕着锚点分大小
            swap(&arr[++i], &arr[j]);
        }
    }
    // 最后把锚点放到中间来
    swap(&arr[i + 1], &arr[high]);
    //返回锚点的位置
    return i + 1;
}

patition函数的作用可以单独来看，其功能是将一个区间分为3部分，锚点、左、右，如何在一次for循环中搞定这个事情呢？

首先是设定锚点，使用区间最右边的值作为锚点，然后遍历区间每一个数x，如果x小于锚点，就将x与左边的哨兵进行交换，因为x的位置肯定大于等于哨兵位置，所以交换不会产生副作用。最后将锚点交换到哨兵的下一个位置，完成分区任务。

一秒记忆

一句话记忆：将小于锚点的数放到左边

这句话和我们之前的一篇文章核心部分非常相似，也非常精巧，那就是Knuth随机算法，那个算法也是一句话记忆：将当前数与当前区间的一个数进行交换。

事实上，快速排序算法精巧的地方也在于一次for循环完成任务。如果你能理解Knuth随机算法的那一次for循环，那么理解快速排序甚至要简单一点。

大师的手段如出一辙。

动画解说

上面的代码用python原班实现，做成了如下动画：

总结

对于快速排序算法，核心部分其实只有两三行代码，可是在很久以前学习的时候却感觉很困难，而现在看又有一种简单的感觉，孔子说过温故而知新，也许就是这个道理。