排序算法全解析

$1984$1984 年，加拿大数学家亚历山大·杜德尼（Alexander Dewdney）在「Scientific American」杂志上发表了意大利面排序算法（Spaghetti sort）。

意大利面排序：

• 首先，取一把未煮的意大利面，对于数组中的每一个数字，剪一根对应长度的意大利面条，用这根面条代表这个数字。

• 用一只手拿着这一把面条，将其竖着立在桌子上，保证每一根的底部都碰到桌面。另一只手从面条的上方缓缓下落。显然，这只手碰到的第一根面条就是最长的，将其取出放至首位。重复此过程直至所有的面条取完，数字就完成了排序。

为什么要用意大利面呢？兰州拉面请求出战可不可以？

这或许是因为意大利面是由小麦品种中最硬质的杜兰（durum）磨粉制成，较为坚硬，在桌上立得稳～

从排序流程可以看出，意大利面排序并不是什么新鲜的算法，它类似于「计数排序」章节中介绍的「伪计数排序」。

• Java

public static void spaghettiSort(int[] arr) {
    // 假设数字大小都在 1～9 之间，准备一把长度在 1～9cm 之间的面条，用面条的长度记录数字大小。
    // 注：为了便于理解，新建长度为 10 的数组，只使用数组的 1～9 位，不使用数组的第 0 位
    int[] spaghettiLength = new int[10];
    // 遍历数组中的每个数字
    for (int element : arr) {
        // 将每个数字的大小反映成面条的长短
        spaghettiLength[element]++;
    }
    // 右手从高处落下，碰到的第一根面条对应的数字就是最大的数字，重复此过程直到排序完成
    for (int i = 9, index = 0; i >= 1; i--) {
        while (spaghettiLength[i] != 0) {
            spaghettiLength[i]--;
            arr[index++] = i;
        }
    }
}

由于「Scientific American」是美国发行的科普杂志，所以笔者猜测此算法诞生的目的是用通俗的方式向大众普及算法的魅力，每位读者都可以在家中轻易地做此实验。

时间复杂度 & 空间复杂度

排序过程类似计数排序，时间复杂度 $O(n+k)$O(n+k)（k 表示数据范围），空间复杂度 $O(k)$O(k)（k 表示数据范围）。