气泡排序与选择排序
气泡排序是一种分类算法,它通过浏览列表来重复排序时,同时比较相邻的元素对。如果一对元素处于错误的顺序上,则将它们换成正确的顺序。重复此遍历,直到不需要进一步掉期为止。选择排序也是一种排序算法,首先要查找列表中的最小元素并与第一个元素交换。通过将交换元素按顺序放置,对列表的其余部分重复此过程。
什么是泡泡?
气泡排序是一种分类算法,它通过浏览列表来重复排序时,同时比较相邻的元素对。如果一对元素处于错误的顺序上,则将它们换成正确的顺序。重复此遍历,直到不需要进一步的掉期(这意味着列表已排序)。由于列表中较小的元素随着气泡的表面浮出水面而到达顶部,因此将其称为气泡排序。气泡排序是一种非常简单的排序算法,但是在用n个元素排序列表时,它具有O(n2)的平均情况时间复杂性。因此,气泡排序不适合与大量元素的分类列表。但是,由于其简单性,在对算法的介绍期间进行了泡泡排序。
什么是选择排序?
选择排序也是另一种排序算法,首先要查找列表中的最小元素并与第一个元素交换。然后从列表的其余部分(从第二个元素到列表中的最后一个元素)找到最小元素,并与第二个元素互换。通过将交换元素按顺序放置,对列表的其余部分重复此过程。因此,在选择中,在算法的任何步骤中,列表分为两个部分,其中一个部分包含排序的元素,另一部分包含未分类的元素。随着算法的进行,排序的列表从左到右生长。选择排序还具有O(n2)的平均案例时间复杂性。因此,它也不适合对大型列表进行排序。
气泡排序和选择排序有什么区别?
即使气泡排序和选择排序算法都具有O(n2)的平均案例时间复杂性,但对于选择排序,气泡排序几乎均超过了。这是由于两种算法所需的互换数量(气泡类别需要更多掉期)。但是由于气泡排序的简单性,其代码大小很小。稳定性是这两种算法的另一个区别。稳定的排序算法是一种排序算法,如果列表包含具有相等值的元素,则保留记录顺序。从这个意义上讲,选择排序不是稳定的算法,而气泡排序是一种稳定的算法。
发表评论