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

Question

任何人都可以向我解释维基百科上排序算法的“图形说明”是什么意思吗？我无法理解他们。

冒泡排序

插入排序

Answer 1

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

这里的区别在于，冒泡排序会采用单个元素并开始交换相邻元素(因此您可以看到深灰色元素慢慢传播到末尾，直到它遇到一个更暗的元素，然后您继续那个元素).

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

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

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