《算法（第4版）》笔记

归并

归并排序基于“归并”这个简单的操作，即将两个有序的数组归并成一个更大的有序数组。

要将一个数组排序，可以先（递归地）将它分成两半分别排序，然后将结果归并起来。

// c++
template<class T>
void merge(T& a, int lo, int mid, int hi, T& aux)
{
    // 将a[lo .. mid]和a[mid+1 .. hi]归并
    int i = lo;
    int j = mid + 1;

    for (int k=lo; k<=hi; ++k)
        aux[k] = a[k];

    for (int k=lo; k<=hi; ++k)
    {
        if (i > mid)
            a[k] = aux[j++];
        else if (j > hi)
            a[k] = aux[i++];
        else if (aux[j] < aux[i])
            a[k] = aux[j++];
        else
            a[k] = aux[i++];
    }
}

# python
def merge(a, lo, mid, hi, aux):
    # 将a[lo .. mid]和a[mid+1 .. hi]归并
    i = lo
    j = mid + 1

    for k in range(lo, hi + 1):
        aux[k] = a[k]

    for k in range(lo, hi + 1):
        if i > mid:
            a[k] = aux[j]
            j += 1
        elif j > hi:
            a[k] = aux[i]
            i += 1
        elif aux[j] < aux[i]:
            a[k] = aux[j]
            j += 1
        else:
            a[k] = aux[i]
            i += 1

自顶向下的归并排序（递归）

// c++
template<class T>
void merge_sort(T& a, int lo, int hi, T& aux)
{
    if (hi <= lo)
        return;

    int mid = lo + (hi - lo) / 2;
    merge_sort(a, lo, mid, aux);      // 将左半边排序
    merge_sort(a, mid + 1, hi, aux);  // 将右半边排序
    merge(a, lo, mid, hi, aux); // 归并结果
}

// 将容器a按升序排列
template<class T>
void merge_sort(T& a)
{
    T aux;
    aux.resize(a.size());
    merge_sort(a, 0, a.size() - 1, aux);
}

# python
def merge_sort_p(a, lo, hi, aux):
    if hi <= lo:
        return

    mid = lo + (hi - lo) // 2
    merge_sort_p(a, lo, mid, aux)
    merge_sort_p(a, mid + 1, hi, aux)
    merge(a, lo, mid, hi, aux)

# 将列表a按升序排列
def merge_sort(a):
    aux = [None] * len(a)
    merge_sort_p(a, 0, len(a) - 1, aux)

归并排序所需的时间和NlogN成正比。

可以用归并排序处理数百万甚至更大规模的数组，这是插入排序或者选择排序做不到的。归并排序的主要缺点是辅助数组所使用的额外空间和N的大小成正比。

通过一些细致的思考我们还能够大幅度缩短归并排序的运行时间，比如对小规模子数组使用插入排序。使用插入排序处理小规模的子数组（比如长度小于15）一般可以将归并排序的运行时间缩短10%~15%。

自底向上的归并排序

实现归并排序的另一种方法是先归并那些微型数组，然后再成对归并得到的子数组，如此这般，直到我们将整个数组归并在一起。这种实现方法比标准递归方法所需要的代码量更少。首先我们进行两两归并（把每个元素想象成一个大小为1的数组），然后是四四归并（将两个大小为2的数组归并成一个有4个元素的数组），然后是八八归并，一直下去。

// c++
// 将容器a按升序排列
template<class T>
void mergeBU_sort(T& a)
{
    int n = a.size();

    T aux;
    aux.resize(n);

    for (int sz = 1; sz < n; sz += sz)
        for (int lo = 0; lo < n - sz; lo += sz + sz)
            merge(a, lo, lo + sz - 1, std::min(lo + sz + sz - 1, n - 1), aux);
}

# python
# 将列表a按升序排列
def mergeBU_sort(a)
    n = len(a)
    aux = [None] * n

    sz = 1
    while sz < n:
        for lo in range(0, n - sz, sz + sz):
            merge(a, lo, lo + sz -1, min(lo + sz + sz - 1, n - 1), aux)
        sz += sz

《算法（第4版）》笔记

选择排序

首先，找到数组中最小的那个元素，其次，将它和数组的第一个元素交换位置（如果第一个元素就是最小元素那么它就和自己交换）。再次，在剩下的元素中找到最小的元素，将它与数组的第二个元素交换位置。如此往复，直到将整个数组排序。这种方法叫做选择排序，因为它在不断地选择剩余元素之中的最小者。

选择排序的缺点：一个已经有序的数组或是主键全部相等的数组和一个元素随机排列的数组所用的排序时间竟然一样长。

// c++
// 将容器a按升序排列
template<class T>
void selection_sort(T& a)
{
    int n = a.size();
    for (int i=0; i<n; ++i)
    {
        int min = i;
        for (int j=i+1; j<n; ++j)
        {
            if (a[j] < a[min])
                min = j;
        }

        std::swap(a[i], a[min]);
    }
}

# python
# 将列表a按升序排列
def selection_sort(a):
    n = len(a)
    for i in range(n):
        min = i
        for j in range(i+1, n):
            if a[j] < a[min]:
                min = j

        a[i], a[min] = a[min], a[i]

插入排序

通常人们整理桥牌的方法是一张一张的来，将每一张牌插入到其他已经有序的牌中的适当的位置。在计算机的实现中，为了给要插入的元素腾出空间，我们需要将其余所有元素在插入之前都向右移动一位。这种算法叫做插入排序。

和选择排序不同的是，插入排序所需的时间取决于输入中元素的初始顺序。例如，对一个很大的其中的元素已经有序（或接近有序）的数组进行排序将会比对随机顺序的数组或是逆序数组进行排序要快得多。

插入排序对于部分有序的数组十分高效，也很适合小规模数组。

在1980年本书第1版完成之时插入排序就比选择排序快一倍，现在仍然是这样。

// c++
// 将容器a按升序排列
template<class T>
void insertion_sort(T& a)
{
    int n = a.size();
    for (int i=1; i<n; ++i)
    {
        for (int j=i; j>0 && a[j]<a[j-1]; --j)
            std::swap(a[j], a[j-1]);
    }
}

# python
# 将列表a按升序排列
def insertion_sort(a):
    n = len(a)
    for i in range(1, n):
        for j in range(i, 0, -1):
            if a[j] < a[j-1]:
                a[j], a[j-1] = a[j-1], a[j]
            else:
                break

希尔排序

希尔排序是一种基于插入排序的快速的排序算法。

对于大规模乱序数组插入排序很慢，因为它只会交换相邻的元素，因此元素只能一点一点地从数组的一端移动到另一端。希尔排序为了加快速度简单地改进了插入排序，交换不相邻的元素以对数组的局部进行排序，并最终用插入排序将局部有序的数组排序。

希尔排序的思想是使数组中任意间隔为h的元素都是有序的。这样的数组被称为h有序数组。换句话说，一个h有序数组就是h个互相独立的有序数组编织在一起组成的一个数组（见图2.1.2）。在进行排序时，如果h很大，我们就能将元素移动到很远的地方，为实现更小的h有序创造方便。用这种方式，对于任意以1结尾的h序列，我们都能够将数组排序。这就是希尔排序。使用的h序列被称为递增序列。

（如上图所示，当h=4时，即间隔为4，整个数组分为4个子数组，分别对4个子数组使用插入排序进行排序。h的取值不断减小，当为1时，排序后整个数组变为有序，排序结束。）

// c++
// 将容器a按升序排列
template<class T>
void shell_sort(T& a)
{
    int n = a.size();

    // 递增序列 1, 4, 13, 40, 121, ...
    // 确定h初始值
    int h = 1;
    while (h < n/3)
        h = 3 * h + 1;

    while (h >= 1)
    {
        // 将数组变为h有序
        for (int i=h; i<n; ++i)
        {
            for (int j=i; j>=h && a[j] < a[j-h]; j-=h)
                std::swap(a[j], a[j-h]);
        }

        h = h / 3;
    }
}

# python
# 将列表a按升序排列
def shell_sort(a):
    n = len(a)

    # 递增序列 1, 4, 13, 40, 121, ...
    # 确定h初始值
    h = 1
    while h < n / 3:
        h = 3 * h + 1

    while h >= 1:
        # 将数组变为h有序
        for i in range(h, n):
            for j in range(i, h-1, -h):
                if a[j] < a[j-h]:
                    a[j], a[j-h] = a[j-h], a[j]
                else:
                    break

        h = h // 3

如何选择递增序列呢？要回答这个问题并不简单。算法的性能不仅取决于h，还取决于h之间的数学性质，比如它们的公因子等。有很多论文研究了各种不同的递增序列，但都无法证明某个序列是“最好的”。

和选择排序以及插入排序形成对比的是，希尔排序也可以用于大型数组。它对任意排序（不一定是随机的）的数组表现也很好。

希尔排序比插入排序和选择排序要快得多，并且数组越大，优势越大。

目前最重要的结论是它的运行时间达不到平方级别。

摘自《基督山伯爵》

三个月前，唐戴斯一心只想着自由，现在光有自由不够了，他还渴望财富；要说过错，那不在唐戴斯，而在天主，它限制了人的能力，却给了他无穷的欲望！

至于您，莫雷尔，我要告诉您的秘密是：这个世界上无所谓幸福，也无所谓不幸，有的只是一种境况和另一种境况的比较，如此而已。只有体验过极度不幸的人，才能品尝到极度的幸福。只有下过死的决心的人，马克西米利安，才会知道活着有多好。

幸福地生活下去吧，我心爱的孩子们，请你们永远别忘记，直至天主垂允为人类揭示未来图景的那一天来到之前，人类的全部智慧就包含在这五个字里面：

等待和希望！

摘自《肖申克的救赎》

我当然记得那个小镇的名字，圣华塔尼欧，这名字太美了，令人忘不了。

我发现自己兴奋莫名，颤抖的手几乎握不住笔。我想惟有自由人才能感受到这种兴奋，一个自由人步上漫长的旅程，奔向不确定的未来。

我希望安迪在那儿。

我希望我能成功跨越美墨边界。

我希望能见到我的朋友，和他握握手。

我希望太平洋就和我梦中所见的一样蔚蓝。

我希望……

摘自《Python基础教程》

虽然这里提倡使用原型，但务必对推倒重来持谨慎态度，在你为编写原型投入了不少时间和精力时尤其如此。更好的选择可能是，对原型进行重构和修改，让其变成功能上更好的系统，其原因有多个。

一个可能出现的常见问题是“第二系统综合征”，即力图让第二个版本非常灵巧或完美无缺，导致永远没有完工的时候。

“不断重写综合征”在小说创作领域很常见，指的是不断地修改程序，甚至推倒重来。在有些情况下，让程序“还行”可能是最佳的策略——管用就好。

还有“代码疲劳症”，即你对代码逐渐感到厌烦。你花了很长时间来编写代码，却发现它丑陋而笨拙。导致代码看起来粗糙而笨拙的原因之一是，必须处理各种特殊情况并包含多种形式的错误处理等。无论如何，在新版本中也必须包含这些功能，而最初为了实现它们，你可能花了很大的精力（更别说为调试花费的精力了）。

换而言之，如果你觉得原型还有得救，能变成可行的系统，就应竭尽所能地修改它，而不是推倒重来。在本书后面关于开发项目的章节中，我将开发成果分成了界线清晰的两个版本：原型和最终程序。这样做既是出于清晰考虑，也是为了突出通过编写软件的第一个版本获得的经验和洞察力。在实际开发工作中，完全可以先开发原型，再通过重构它来获得最终的系统。

要深入地了解推倒重来的恐怖之处，请参阅Joel Spolsky撰写的文章“Things You Should Never Do, Part I”（joelonsoftware.com）。据Spolsky讲，对所有软件公司来说，推倒重来都是最严重的策略性错误。