algorithm - 维基百科上的排序算法插图？

Question

谁能向我解释维基百科上排序算法的“图形插图”是什么意思？我无法理解他们。

冒泡排序

插入排序

Answer 1

这些是数组中各种元素的位置（看起来灰色调表示数值）。线条显示了排序的过程，X 轴是时间，并且在每个时间步长上移动一个或多个元素，直到在右侧您可以看到它们按音调排序。

这里的区别在于冒泡排序将采用单个元素并开始交换相邻元素（因此您可以看到深灰色元素缓慢传播到最后，直到它遇到更暗的元素，然后您继续使用那个元素）。

另一方面，插入排序采用单个元素，决定插入它的位置，并相应地移动其余元素，您可以看到这由几条同时移动的平行对角线表示。

这是一个很好的插图，但请尝试阅读算法描述 - 它不是很复杂，也许这样插图对您来说更有意义。

这些插图的另一个可能的好处是，它们可能会让您预感对数组进行排序所需的操作数量——即使它是针对单个给定示例，不一定是最坏的情况。冒泡排序和插入排序的大小都是 O(n^2)，n 是元素的数量。这意味着随着 n 的增长，您正在研究相当多的操作（交换或插入）。这就是为什么他们提出了其他具有更好复杂性的排序算法（高达 O(n*logn)，在一般情况下你无法击败它），例如快速排序；以及依赖于附加约束的算法，例如排序数字从上方有界（bin sort / radix sort）