5.8.选择排序
Last updated
Last updated
选择排序改进了冒泡排序,每次遍历列表只做一次交换。为了做到这一点,一个选择排序在他遍历时寻找最大的值,并在完成遍历后,将其放置在正确的位置。与冒泡排序一样,在第一次遍历后,最大的项在正确的地方。 第二遍后,下一个最大的就位。遍历 n-1 次排序 n 个项,因为最终项必须在第(n-1)次遍历之后。
Figure 3 展示了整个排序过程。在每次遍历时,选择最大的剩余项,然后放置在其适当位置。第一遍放置 93,第二遍放置 77,第三遍放置 55 等。 该函数展示在 ActiveCode 1 中。
Activecode 1
你可能会看到选择排序与冒泡排序有相同数量的比较,因此也是 O(n^2 )。 然而,由于交换数量的减少,选择排序通常在基准研究中执行得更快。 事实上,对于我们的列表,冒泡排序有 20 次交换,而选择排序只有 8 次。