Summary of Sorting Algorithms


 

Summary of Sorting Algorithms

排序算法总结

0x00. TOC

选择排序

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

代码实现如下所示,选择排序的内循环只是在比较当前元素与目前已知的最小元素(以及将当前索引加 1 和检查是否代码越界),这已经简单到了极点。交换元素的代码写在内循环之外,每次交换都能排定一个元素,因此交换的总次数是 N。所以算法的时间效率取决于比较的次数。对于长度为 N 的数组,选择排序需要大约 N2/2 次比较和 N 次交换。

public static void sort(Comparable[] a) {
        int n = a.length;
        for (int i = 0; i < n; i++) {
            int min = i;
            for (int j = i+1; j < n; j++) {
                if (less(a[j], a[min])) min = j;
            }
            exchange(a, i, min);
            assert isSorted(a, 0, i);
        }
        assert isSorted(a);
}

选择排序是一种很容易理解和实现的简单排序算法,它有两个很鲜明的特点。

  • 运行时间和输入无关: 为了找出最小的元素而扫描一遍数组并不能为下一遍扫描提供什么信息。这种性质在某些情况下是缺点,因为使用选择排序的人可能会惊讶地发现,一个已经有序的数组或是主键全部相等的数组和一个元素随机排列的数组所用的排序时间竟然一样长!我们将会看到,其他算法会更善于利用输入的初始状态。
  • 数据移动是最少的: 每次交换都会改变两个数组元素的值,因此选择排序用了 N 次交换——交换次数和数组的大小是线性关系。我们将研究的其他任何算法都不具备这个特征(大部分的增长数量级都是线性对数或是平方级别)。

冒泡排序

冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。TOC

冒泡排序对 n个项目需要进行 O(n2) 次比较,且支持原地排序。尽管该算法是最简单了解和实现的排序算法之一,但它对于包含大量的元素的数列排序是很没有效率的。

冒泡排序是与插入排序拥有相等的运行时间,但是两种算法在需要的交换次数却很大地不同。在最坏的情况,冒泡排序需要 n2 次交换,而插入排序只要最多 O(n) 交换。冒泡排序的实现通常会对已经排序好的数列拙劣地运行 O(n2),而插入排序在这个例子只需要 O(n) 个运算。因此很多现代的算法教科书避免使用冒泡排序,而用插入排序取代之。下面是冒泡排序的操作过程及实现:

  1. 比较相邻的元素。如果第一个比第二个大,就交换他们两个。
  2. 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。这步做完后,最后的元素会是最大的数。
  3. 针对所有的元素重复以上的步骤,除了最后一个。
  4. 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。
public static void sort(Comparable[] input) {
    int n = input.length;
    // 每排完一趟,将一个当前趟中最大的元素冒泡到i位置, i左移,其右边排好序
    for (int i = (n - 1); i > 0; i--) {
        for (int j = 0; j < i-1; j++) {
            if (less(input[j + 1], input[j])) {
                exchange(input, j, j+1);
            }
        }
    }
    assert isSorted(input);
}

使用标记i记录最大或最小的元素应该在位置,每排完一趟,将一个当前趟中最大的元素冒泡到i位置, i左移,其右边排好序,不再参与下一趟的排序判断。不同于上面的代码实现,下面给出的示例图中,采用的方式是把最小元素向左冒泡,而不是吧最大元素向右冒泡,但原理是一样的。

鸡尾酒排序

是冒泡排序的一种变形。此算法与冒泡排序的不同处在于排序时是以双向在序列中进行排序。鸡尾酒排序等于是冒泡排序的轻微变形。不同的地方在于从低到高然后从高到低,而冒泡排序则仅从低到高去比较序列里的每个元素。它可以得到比冒泡排序稍微好一点的性能,原因是冒泡排序只从一个方向进行比对(由低到高),每次循环只移动一个项目。TOC

以序列(2,3,4,5,1)为例,鸡尾酒排序只需要访问一次序列就可以完成排序,但如果使用冒泡排序则需要四次。但是在随机数序列的状态下,鸡尾酒排序与冒泡排序的效率都很差劲。鸡尾酒排序最糟或是平均所花费的次数都是 O(n2},但如果序列在一开始已经大部分排序过的话,会接近 O(n)。

public static void sort(Comparable[] arr) {
    int i, left = 0, right = arr.length - 1;
    while (left < right) {
        // 从低到高,把每趟的最大值冒泡到右端
        for (i = left; i < right; i++) {
            if (less(arr[i+1], arr[i])) {
                exchange(arr, i, i + 1);
            }
        }
        right--;
        // 从高到低,把每趟的最小大冒泡到左端
        for (i = right; i > left; i--) {
            if (less(arr[i], arr[i-1])) {
                exchange(arr, i, i - 1);
            }
        }
        left++;
    }
    assert isSorted(arr);
}

看上面代码中可以很明显地看到两个 for 循环的逻辑其实就是基于冒泡排序的逻辑,只不过将单向的冒泡排序改成了双向的,通过设置leftright控制冒泡的位置以及结束时机。

插入排序

为了给要插入的元素腾出空间,将其余所有元素在插入之前都右移一位。这种算法叫做插入排序。示例过程参照下面的两个动图。与选择排序一样,当前索引左边的所有元素都是有序的,但它们的最终位置还不确定,为了给更小的元素腾出空间,它们可能会被移动。但是当索引到达数组的右端时,数组排序就完成了。和选择排序不同的是,插入排序所需的时间取决于输入中元素的初始顺序。例如,对一个很大且其中的元素已经有序(或接近有序)的数组进行排序将会比对随机顺序的数组或是逆序数组进行排序要快得多。TOC

对于随机排列的长度为 N 且主键不重复的数组,平均情况下插入排序需要 ~N2/4 次比较以及 ~N2/4 次交换。最坏情况下需要 ~N2/2 次比较和 ~N2/2 次交换,最好情况下需要 N-1 次比较和 0 次交换。

public static void sort(Comparable[] a) {
        int n = a.length;
        for (int i = 1; i < n; i++) {
            for (int j = i; j > 0 && less(a[j], a[j-1]); j--) {
                exchange(a, j, j-1);
            }
            assert isSorted(a, 0, i);
        }
        assert isSorted(a);
}

对于 0 到 N-1 之间的每一个 i,将 a[i] 与 (a[0], a[i-1]) 区间中比它小的所有元素依次有序地交换。在索引 i 由左向右变化的过程中,它左侧的元素总是有序的,所以当 i 到达数组的右端时排序就完成了。

希尔排序

希尔排序是一种基于插入排序的快速的排序算法。对于大规模乱序数组插入排序很慢,因为它只会交换相邻的元素,因此元素只能一点一点地从数组的一端移动到另一端。例如,如果主键最小的元素正好在数组的尽头,要将它挪到正确的位置就需要 N-1 次移动。希尔排序为了加快速度简单地改进了插入排序,交换不相邻的元素以对数组的局部进行排序,并最终用插入排序将局部有序的数组排序。

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

下面算法的实现使用了Pratt在1971年提出的间隙序列公式 12 *(3k-1),在 k>=1的前提下,间隙序列的元素的最大值不超过N/3,其中N是待排序数组的长度,该间隙序列的实际值是{1, 4, 13, 40, 121, 364, 1093, ...},前后两个项目间存在关系 Si+1 = 3 * Si + 1,利用这个关系我们计算出见徐序列中的最大元素h,然后利用该元素开始进行排序,每走完一遍待排序的数组,将h缩小3倍并向下取整,如此往复,直到h=1

下面算法实时计算了它的递增序列,另一种方式是将递增序列存储在一个数组中,然后在第二个while loop中取出相应的间隙数据,用空间换些许时间。TOC

public static void sort(Comparable[] a) {
    int n = a.length, h = 1;

    // 3x+1 increment sequence:  1, 4, 13, 40, 121, 364, 1093, ... 
    while (h < n/3) 
        h = 3*h + 1; 

    while (h >= 1) {
        // h-sort the array
        for (int i = h; i < n; i++) {
            for (int j = i; j >= h && less(a[j], a[j-h]); j -= h) {
                exchange(a, j, j-h);
            }
        }
        assert isHsorted(a, h); 
        h /= 3;
    }
    assert isSorted(a);
}

实现希尔排序的一种方法是对于每个 h,用插入排序将 h 个子数组独立地排序。但因为子数组是相互独立的,一个更简单的方法是在 h- 子数组中将每个元素交换到比它大的元素之前去(将比它大的元素右移一格)。只需要在插入排序的代码中将移动元素的距离由 1 改为 h 即可。这样,希尔排序的实现就转化为了一个类似于插入排序但使用不同增量的过程。

下面基于上述的算法,通过打印每次非1间隙得到的子集,以及其他输出序列进行理解,为了便于直观理解算法逻辑,其中打印代码并没出现在上面的的代码块中,同时因为当间隙h=1时希尔排序变成了插入排序,所以在此并没有给出h=1时的输出序列。

input data: [13, 14, 94, 33, 82, 25, 59, 94, 65, 23, 45, 27, 73, 25, 39, 10]
gaps: [1, 4, 13]

before sorting, h=13
13 14 94 33 82 25 59 94 65 23 45 27 73
25 39 10 
after sorting, h=13
13 14 10 33 82 25 59 94 65 23 45 27 73
25 39 94 

before sorting, h=4
13 14 10 33
82 25 59 94
65 23 45 27
73 25 39 94
after sorting, h=4
13 14 10 27
65 23 39 33
73 25 45 94
82 25 59 94
sorted data: [10, 13, 14, 23, 25, 25, 27, 33, 39, 45, 59, 65, 73, 82, 94, 94]

可以看到,当h=13时,存在三个间隙子集,分别是{13, 25}{14, 39}{94, 10},其实即对应上面输出序列的前三列,易见{94, 10}被排序为{10, 94}。同理,当间隙h=4时可见,4个间隙都发生了排序。当间隙h=4时,序列的有序性已经非常高,此时的排序逻辑与插入排序一致。下面给出两个示例动画:

归并排序

要将一个数组排序,可先递归地将它分成两半分别排序,然后将结果归并起来。在性能方面,优点是可以保证任意长度为 N 的数组排序所需时间和 NlogN 成正比,即用大O符号表示为O(nlogn),而缺点是它需要额外开辟的空间和 N 成正比,即空间复杂度为O(n)。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用,且各层分治递归可以同时进行。归并排序中极重要的一个操作是归并,下面介绍两种归并方法TOC

  • 递归法(Top-down)
    1. 申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列。
    2. 设定两个指针,最初位置分别为两个已经排序序列的起始位置。
    3. 比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置。
    4. 重复步骤3直到某一指针到达序列尾。
    5. 将另一序列剩下的所有元素直接复制到合并序列尾。
  • 迭代法(Bottom-up)
    1. 假设序列共有n个元素
    2. 将序列每相邻两个数字进行归并操作,形成ceil(n/2)个序列,排序后每个序列包含两/一个元素
    3. 若此时序列数不是1个则将上述序列再次归并,形成 ceil(n/4)个序列,每个序列包含四/三个元素
    4. 重复步骤2,直到所有元素排序完毕,即序列数为1

参考上述步骤可知,实现归并的最直接的方法是讲两个不同的有序数组归并到第三个数组中,然而需要考虑到的是当用归并将一个大数组排序时,需要进行多次归并,因此每次归并时都创建一个新数组来存储排序结果会带来问题,因此在《Algorithm》中提到了一种能够原地归并的方法,即先将待排序数组分成前后两半部分进行排序,然后在数组中移动元素而不需要使用额外空间。大概的思路是:

  • 分半(Divide):采用分治思想,将待排序数组分成两个或更多的子数组(自顶向下),
  • 递归:递归分割到子数组的元素只有一个。
  • 合并(Conquer):在每轮递归完向上合并已排好序的子数组,结果仍保存到原数组中(原地归并)。

img

上图大概给出归并排序的分治过程,下面是基于原地归并和自顶向下分治的递归实现:

private static void merge(Comparable[] a, Comparable[] aux, int lo, int mid, int hi) {
    // precondition: a[lo .. mid] and a[mid+1 .. hi] are sorted subarrays
    assert isSorted(a, lo, mid);
    assert isSorted(a, mid + 1, hi);

    // 复制原数组的部分内容到辅助数组中
    for (int k = lo; k <= hi; k++) {
        aux[k] = a[k]; 
    }

    // merge back to a[]
    // 设定两个指针,最初位置分别为两个已经排序序列的起始位置。
    int i = lo, j = mid + 1;
    // 比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置。
    for (int k = lo; k <= hi; k++) {
        if      (i > mid)              a[k] = aux[j++];
        else if (j > hi)               a[k] = aux[i++];
        else if (less(aux[j], aux[i])) a[k] = aux[j++];
        else                           a[k] = aux[i++];
    }

    // postcondition: a[lo .. hi] is sorted
    assert isSorted(a, lo, hi);
}

// mergesort a[lo..hi] using auxiliary array aux[lo..hi]
private static void sort(Comparable[] a, Comparable[] aux, int lo, int hi) {
    // 当子数组中只有一个元素时,不用合并直接返回调用栈
    if (hi <= lo) return;
    // 计算中间点,用右移加速
    int mid = lo + ((hi - lo) >> 2);
    // 左右分治
    sort(a, aux, lo, mid);
    sort(a, aux, mid + 1, hi);
    // 下层递归调用点已经在原数组a中归并完,最底层的嗲用是两个元素的归并
    merge(a, aux, lo, mid, hi);
}

/**
 * Rearranges the array in ascending order, using the natural order.
 * @param a the array to be sorted
 */
public static void sort(Comparable[] a) {
    // 原地归并,定义辅助数组(auxiliary array)
    Comparable[] aux = new Comparable[a.length];
    sort(a, aux, 0, a.length-1);
    assert isSorted(a);
}

merge方法中先将所有元素复制到辅助数组aux[]中,然后再归并回原数组a[]中,在第二个for循环中进行了4个条件判断,它们都跟两半部分中的指针移动有关:

  • 当左半边用尽时,取右半边的元素
  • 当右半边用尽时,取左半边的元素
  • 当右半边的当前元素小于左半边的当前元素时,取右半边的元素(当前元素被相应指针指定)
  • 当右半边的当前元素大于等于左半边的当前元素时,取左半边的元素(当前元素被相应指针指定)

上面给出了两个分别给出基于平均时间复杂度和最坏时间复杂度的两个例子,可以看到在第二层起,每个单元格中的元素时有序的,而单元格间的元素是无序的,需要在合并操作中将它们排好序放到一个合并的单元格中。

快速排序

实现简单,一般应用比其他排序算法都要快得多,另外一个诱人的特点是支持原地排序,只需一个很小的辅助栈,且将长度为 N 的数组排序的时间和 NlgN 成正比,其他的排序算法无法结合这两个特点。另外,快排的内循环比大多数排序算法都短小。其主要缺点是脆弱性,错误的实现会带来低劣的性能。TOC

快排采用了分治的思想,先将数组分成两个子数组,对这两部分分别进行排序。快排与归并排序是互补的,归并排序将数组分成两个子数组分别进行排序,并将有序的子数组归并以将整个数组排序,而快排将数组排序的方式则是当两个子数组都有序时整个数组也就自然有序了。在归并排序中,一个数组被切分成两半,递归调用发生在处理整个数组之前;而在快排中,切分的位置取决于数组的内容,且递归调用发生在处理整个数组之后。

img

在上图中,将K作为分割点,第一次递归结束后,得到的结果如上所示,可见K最终被放到了一个合适的位置,它将不再移动,下面的排序则是在k左右的两块区域里递归进行,而这两块区域中的元素分别小于和大于K,因此易知当这两块区域的有序后,整个数组都有序了。分治实现代码如下所示:

/**
 * Rearranges the array in ascending order, using the natural order.
 * @param a the array to be sorted
 s*/
public static void sort(Comparable[] a) {
    StdRandom.shuffle(a);	// 打乱数据,消除对输入的依赖
    sort(a, 0, a.length - 1);
    assert isSorted(a);
}

// quicksort the subarray from a[lo] to a[hi]
private static void sort(Comparable[] a, int low, int high) {
    if (high <= low) return;
    int j = partition(a, low, high);
    sort(a, low, j-1);	// 将左半部分排序
    sort(a, j+1, high);		// 将右半部分排序
    assert isSorted(a, low, high);
}

快速排序递归地将子数组 a[low, high] 排序,先用 partition()方法将a[j]放到一个合适的位置,然后再用递归调用将其他位置的元素排序。如下图中,通过 partition()方法将数组的第一个元素作为pivot,即中轴点放到一个最终位置a[j]。该方法的关键在于切分,切分结束使得数组满足下面三个条件:

  • 对于某个j,a[j] 已经排定
  • a[low] 到 a[j-1] 中的所有元素都不大于 a[j]
  • a[j] 到 a[high] 中所有元素都不小于 a[j]

因为每个切分过程总是能排定一个元素,用归纳法不难证明递归可正确地将数组排序:若左右子数组均有序,那么由左子数组、切分元素和右子数组组成的结果数组一定是有序的。

要完成切分方法,一般的做法是随意选取a[low]作为切分元素pivot,即那个会被排定的元素,pivot将数组分成左右两份,接着从左到右扫描数组的左端部分,直到找到一个大于等于pivot的元素a,再从右到左扫描数组的右端部分,直到找到一个小于等于pivot的元素b,交换ab,过程如下图左边所示,如此重复,我们就可保证做指针i的左侧元素都不大于切分元素pivot,右指针j右侧的元素都不小于切分元素pivot,当这两个指针相遇时只需将切分元素a[low]和左子数组最右侧的元素a[j]交换然后返回j即可。

img

切分的具体逻辑如下面的代码块中的partition()所示,它按照a[low]的值v进行切分,当指针ij相遇时主循环退出。在循环中,a[i]小于vi不停右移,a[j]大于vj不停左移,当其中一个指针停下时,通过交换a[i]a[j]保证i左侧的元素都不小于vj右侧的元素都不小于v,当两指针相遇时交换a[low]a[j],切分结束。

// partition the subarray a[low..high] so that a[low..j-1] <= a[j] <= a[j+1..high]
// and return the index j.
private static int partition(Comparable[] a, int low, int high) {
    int i = low, j = high + 1;
    Comparable v = a[low];
    while (true) {
        // find item on low to swap
        while (less(a[++i], v) && i < high);
        // find item on high to swap
        while (less(v, a[--j]) && j > low);
        // check if pointers cross
        if (i >= j) break;
        exchange(a, i, j);
    }
    // put partitioning item v at a[j]
    exchange(a, low, j);
    // now, a[low .. j-1] <= a[j] <= a[j+1 .. high]
    return j;
}

如上面右图所示,选取K作为切分点,指针ij渐次左/右移,直到找到比切分点大/小的元素,交换这两个元素,继续移动,直至相遇,在上面的例子中一共经历了4次交换,其中最后一次交换发生在指针相遇时,将切分点K和左子数组最右侧元素a[j]交换。下面给出两个演示动图,以右图为例,首先选取最右侧的31为切分点pivot,左右指针右/左移,符合条件即换位,最后将切分点放到适当的位置,在这个例子中,十分巧合地,一次partition即将数组排序完成,而无需在子数组中递归分治。

堆排序

堆排序是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构,并同时满足堆积的性质:即子节点的键值或索引总是小于或大于它的父节点。前面已经写过一篇文章 二叉堆及堆排序的Java实现 ,在此对堆排序做个简单的回顾和总结。为了实现堆排序,常见的做法是TOC

  1. 用待排序的数组构造称最大堆
  2. 将根结点和最后一个子结点的值互换,通过heapSize--将数组的最后一个元素从堆中删除,逐层检查,维护最大堆的性质
  3. 重复上述步骤直到操作完根结点

当执行删除堆顶元素的操作时,常用的方式是将其与最末一个叶子结点进行交换,通过heapSize--将数组的最后一个元素从堆中删除,而此时的堆状态可能会违反大顶堆的定义,即父结点的值小于子结点的值,故需要对堆中数据进行重大顶堆化(remaxheapify)操作,通过将小的父结点下降维护大顶堆的性质。下面给出这一过程的实现:

/**
 * Helper functions to restore the heap invariant.
 * @param pq 堆数据存储数组
 * @param k 需要下沉的父结点
 * @param n 堆中的元素个数,用于判断是否操作到叶子结点层
 */
private static void sink(Comparable[] pq, int k, int n) {
    while (2*k <= n) {
        int j = 2*k;
        // 父结点不为叶子结点,同时如果左结点小于右结点
        // 则将指针移向右结点,即将子结点中较大的那个上移
        if (j < n && less(pq, j, j+1)) j++;
        // 左子结点的值不大于父结点的值
        // 并发问题或其他情况导致异常,结束
        if (!less(pq, k, j)) break;
        // 换位
        exchange(pq, k, j);
        // 由于某个子结点移位,导致其对应的子树结构发生了变化
        // 所以需要对这棵子树也进行下沉操作
        k = j;
    }
}

sink()函数通过设置记录待下沉结点的指针来实现各层级的下沉,避免了使用递归的方式,其中的逻辑看注释即可。下面给出堆排序的实现,由于堆数组的索引范围为[1, n]及完全二叉树的性质,所以可以最后一个父结点开始进行下沉操作,可以想象到,当对根结点(k=1)进行下沉操作时,其左子结点(k=2)和右子结点(k=3)已经分别成堆,那么只需对根节点调用sink()函数即可构造出一个完整的堆,当然对根结点的下沉可能需要对其各层子树的结构重新进行调整。

/**
 * Rearranges the array in ascending order, using the natural order.
 * @param pq the array to be sorted
 */
public static void sort(Comparable[] pq) {
    int n = pq.length;
    // 堆数组索引从1开始,0号位置弃用
    // 通过数组内元素的交换实现结点的下沉
    // 从而实现大顶堆的构建
    for (int k = n/2; k >= 1; k--) {
        sink(pq, k, n);
    }
    // 将大顶堆的堆顶元素和最末的叶子结点交换,并恢复堆的性质
    while (n > 1) {
        // 将最末的叶子结点与堆顶元素交换
        // 通过n--操作将此时最末的叶子结点即最大结点的从堆中删除
        // 此结点排序完成
        exchange(pq, 1, n--);
        // 从对顶开始,将较小的元素向下沉
        sink(pq, 1, n);
    }
}

下面给出两个示例动图,以右图为例,对于数组[6, 5, 3, 1, 8, 7, 2, 4],在进行构造堆操作完成后,数组变成[8, 6, 7, 4, 5, 3, 2, 1],完后再进行循环的交换和下沉最后得到有序的序列。

排序算法的复杂度

通过证明可以得出这样一个重要的结论:没有任何基于比较的算法能保证使用少于 lg(N!) ~ NlgN 次比较将长度为 N 的数组排序。该结论表明其他排序算法复杂度的下限。TOC

而对归并排序可以得到的一个结论是:对于长度为 N 的任意数组,自底向下的归并排序需要 12 NlgN 到 NlgN次比较,最多访问数组 6NlgN 次,NlgN 是其他排序算法复杂度的上限。

结合上面的两个结论可以得到:归并排序是一种渐进最优的基于比较排序的算法。更准确地说,归并排序在最坏情况下的比较次数和任意基于比较的排序算法所需的最少比较次数都是 ~NlgN

img

Happy Sorting

首先分享一个估计是密集恐惧症杀手做的看上去颇为牛*的动图

img

下面给出 Youtube 上挺 hot 的一个关于归并排序的舞蹈的视频(需要开梯才能加载),该舞蹈其实属于一个系列,除了归并排序,还有关于冒泡排序等排序算法的舞蹈(见参考链接)。由Kátai Zoltán 和 Tóth László.摄于 Sapientia University,很多美国学校的老师为了增强上课的趣味性都在课堂上播了这些视频,感觉挺有意思,have fun TOC

参考

相关文章