审查和测试排序方法。第一部分

有一天，在 VKontakte 评论中，我与该项目的其他一名学生发生了争执。争论的本质是“谁会赢”——sort()类中的方法java.util.Arrays或简单算法的自写实现：bubble、insert、Selection、shell（Shell 算法）。 对于某些人来说，这个问题的答案可能是显而易见的，但自从争议出现以来，尽管双方都有“受人尊敬的消息来源”支持其观点，但还是决定进行一项研究，将灰质延伸到过程，实现各种算法。 TL;DR： java.util.Arrays.sort() 在 100,000 个或更多元素的数组上，它毫无疑问是领先者；由于尺寸较小，Shell 方法有时可以与之竞争。其余所考虑的算法完全是空的，只有在某些特殊条件下才有用。 现在让我们看看数组在我们的硅超级设备中是如何排序的。

选择排序。按选择排序

让我们从最简单、最明显的方法开始。Robert Sedgwick在coursera 上的视频讲座中向我们完美地展示了它的本质（我将引用那里的 动画，我把它严重压缩成 gif）： 寻找右侧的最小元素，与当前元素交换。因此，我们以排序的形式保留数组的最终版本。下面是用 Java 实现该算法的代码：

public void sort(int[] array) {
        int n = array.length;
        for (int i = 0; i < n; i ++) {
            int minIndex = min(array, i, n - 1);
            swap(array, i, minIndex);
        }
    }

public static void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
public static int min(int[] array, int begin, int end) {
        int minVal = array[begin];
        int minIndex = begin;
        for (int i = begin + 1; i <= end; i++) {
            if (array[i] < minVal) {
                minVal = array[i];
                minIndex = i;
            }
        }
        return minIndex;
    }

算法分析表明，每次遍历都需要对数组的剩余部分进行梳理，也就是说，我们正好需要 N + (N-1) + (N-2) + ... + 1 = N^ 2/2 比较。因此，算法的复杂度为O(N^2)。这是什么意思？这意味着，通过将数组中的元素数量 (N) 增加 2 倍，我们将增加算法的运行时间不是 2 倍，而是 2^2 = 4 倍。通过将 N 增加 10 倍，我们会将操作时间增加 100 倍，依此类推。在我的 2012 年配备 Core i3 处理器、运行 Ubuntu 14.4 的笔记本电脑上，我获得了以下正常运行时间：

插入排序。插入排序

这里的想法略有不同。再次，让我们转向塞奇威克医生的动画： 查看 前面的内容我们甚至还没有看到，而我们留下的一切始终保持秩序。关键是我们将原始数组的每个新元素“返回”到开头，直到它“停留”在较小的元素上。因此，我们再次进行了 N 次遍历（对于原始数组的每个元素），但在每次遍历中，在大多数情况下，我们不会查看整个余数，而只会查看一部分。也就是说，只有当我们必须将每个下一个元素返回到最开始时，即在这种情况下，我们才会得到选项 1 + (N-1) + (N-2) + … + N = N^2/2输入排序的“反向”数组（不幸的是，不幸的是）。在已经排序的数组的情况下（幸运的是），将有一个完整的免费赠品 - 在每次传递中只有一次比较并将元素保留在适当的位置，也就是说，算法将在与 N 成正比的时间内工作。算法的性能将由最坏的理论情况决定，即 O(N^2)。平均而言，运行时间将与N^2/4成正比，即比之前的算法快两倍。在我的实现中，由于排列的非优化使用，运行时间比选择的运行时间更长。我计划尽快纠正并更新该帖子。下面是代码及其在同一台机器上运行的结果：

public void sort(int[] array) {
        int length = array.length;
        for (int i = 1; i < length; i++) {
            for (int j = i; j >= 1; j--) {
                if (array[j] < array[j - 1])
                    swap(array, j, j - 1);
                else
                    break;
            }
        }
    }

贝壳排序。希尔排序

聪明人 Donald Schell 早在 1959 年就注意到，插入算法中最昂贵的情况是元素返回距离数组开头很远的情况：在某些过程中，我们将元素返回到开头几个位置，而在另一遍几乎穿过整个阵列到开始处又远又长。是否可以一次性完成此操作，跳过多个元素？而他找到了这样一个方法。它由顺序执行特殊的部分排序组成，通常称为 d 排序，或者根据 Sedgwick 的说法，称为 h 排序（我怀疑 h 意味着跳跃）。例如，3-sort 不会将有问题的元素与前一个元素进行比较，而是跳过两个元素并与后面 3 个位置的元素进行比较。如果发生变化，它将再次与后面 3 个位置的元素进行比较，依此类推。最重要的是，生成的数组将是“3 排序”的，即元素的错误位置将少于 3 个位置。使用这种插入算法将是轻松愉快的。顺便说一句，“1-sort”只不过是一种插入算法 =) 通过对 h 值递减的数组顺序应用 h-sort，我们可以更快地对大型数组进行排序。它看起来像这样： 查看 这里的挑战是如何选择正确的部分排序顺序。最终，算法的性能取决于此。最常见的是 Donald Knuth 提出的序列：h = h*3 + 1，即 1, 4, 13, 40, ... 等等，最多为数组大小的 1/3。该序列提供了不错的性能并且也易于实现。分析算法需要大量的语言，超出了我的能力。分析的广度还取决于 h 序列的许多变体。根据经验，我们可以说该算法的速度非常好 - 亲自看看： 不到一秒一百万个元素！这是带有 Knut 序列的 Java 代码。

public void sort(int[] array) {
        int h = 1;
        while (h*3 < array.length)
            h = h * 3 + 1;

        while(h >= 1) {
            hSort(array, h);
            h = h/3;
        }
    }

    private void hSort(int[] array, int h) {
        int length = array.length;
        for (int i = h; i < length; i++) {
            for (int j = i; j >= h; j = j - h) {
                if (array[j] < array[j - h])
                    swap(array, j, j - h);
                else
                    break;
            }
        }
    }

冒泡排序。气泡法

这是经典！几乎每个新手程序员都会实现这个算法。这是一部经典之作，塞奇威克博士甚至没有制作动画，所以我必须自己完成这项工作。 在 这里，在每次遍历中，我们从头到尾遍历数组，交换无序的相邻元素。结果，最大的元素“浮动”（因此得名）到数组的末尾。我们乐观地开始每个新的过程，希望数组已经排序（sorted = true）。在段落结束时，如果我们发现自己犯了错误，我们就会开始新的段落。这里的困难在于，我们每次都遍历（几乎）整个数组。比较发生在每一步，交换几乎发生在每一步，这使得该算法成为最慢的算法之一（如果我们考虑合理实现的算法，而不是“摇动排序”和其他类似算法）。有趣的是，形式上这里的复杂度也等于 O(N^2)，但系数远高于插入和选择的系数。算法代码：

public void sort(int[] array) {
        boolean isSorted;
        int nMinusOne = array.length - 1;
        for(int i = 0; i < nMinusOne; i++) {
            isSorted = true;
            for (int j = 0; j < nMinusOne - i; j++) {
                if (array[j] > array[j + 1]) {
                    swap(array, j, j + 1);
                    isSorted = false;
                }
            }
            if (isSorted)
                return;
        }
    }

操作时间： 感受差异：半个多小时处理一百万个元素！结论：永远不要使用这个算法！

第一部分总结

因此，我建议查看这些算法的通用表。 您还可以与内置方法的结果进行比较java.util.Arrays.sort()。它看起来就像某种魔法——还有什么比 Shell 更快呢？我将在下一部分写到这一点。在那里，我们将了解广泛使用的快速排序算法以及合并排序，了解基元和引用类型对数组进行排序的方法的差异，并熟悉这方面的一个非常重要的接口Comparable；）下面您可以学习使用数据表建立在对数刻度上的图表。线条越平坦，算法就越好 =) 对于那些想要下载整个项目并自行运行测试的人，请保留链接： Java 下一部分见！=)