您现在的位置是:首页 >技术交流 >插入排序、选择排序、冒泡排序小结(45)网站首页技术交流

插入排序、选择排序、冒泡排序小结(45)

和猫妹学Python 2024-06-17 11:19:19
简介插入排序、选择排序、冒泡排序小结(45)

小朋友们好,大朋友们好!

我是猫妹,一名爱上Python编程的小学生。

和猫妹学Python,一起趣味学编程。

今日主题

插入排序、选择排序、冒泡排序有什么区别?

原理不同

插入排序是将未排序的元素逐个插入到已排序序列中的合适位置;

选择排序是在已排序序列中找到最小(大)元素,将其放到已排序序列的末尾;

冒泡排序是通过不断比较相邻元素并交换位置来实现排序。

时间复杂度不同

插入排序的时间复杂度为O(n^2),最坏情况下为O(n^2);选

择排序和冒泡排序的时间复杂度均为O(n^2),但在最好情况下都可以达到O(n)。

空间复杂度不同

插入排序的空间复杂度为O(1),只需要常数级别的额外空间;

选择排序和冒泡排序的空间复杂度也为O(1),因为它们都不需要使用额外的空间。

实现难度不同

插入排序相对简单,易于理解和实现;

选择排序也相对简单,但需要额外的存储空间;

冒泡排序的实现较为困难,容易出现超时或溢出的情况。

各自优缺点

插入排序的优点是算法简单,稳定性好,适用于部分已经排好序的数据集;缺点是时间复杂度较高,不适用于大规模数据的排序。

选择排序的优点是时间复杂度较低,适用于小规模数据的排序;缺点是稳定性差,不如插入排序稳定。

冒泡排序的优点是稳定性好,算法简单,适用于大规模数据的排序;缺点是时间复杂度较高,不适用于对实时性要求较高的场景。

 举个例子

请将[1,2,3,4,5]从小到大排列。

插入排序

插入排序把数组分为已排序区和未排序区。

取未排序区的元素,在已排序区上找到一个正确的位置插上去。

选择排序

选择排序也会把数组分为已排序区和未排序区。

但是与插入排序不同的是,它每次找到未排序区的最小值,与未排序区的首个元素交换,这样就变成了已排序区的末尾元素了。

冒泡排序

对于一个数比较与之相邻的数字,例如要把一个数列按从小到大的顺序排列,就拿左边第一个数,和第二的比,若小于第二个数两个交换,否则不换,再比较第二个和第三个,按照同样的规则,继续第三第四…直到最后。这样就算一次冒泡,每次冒泡都会有一个数被放到了最终的位置。

就如下图中这样,图中的下边的数就是我所说的左边的数。

附上一段代码:

 

好了,我们今天就学到这里吧!

如果遇到什么问题,咱们多多交流,共同解决。

我是猫妹,咱们下次见!

文章中的图出自:极客时间上王争课程 —— 数据结构与算法之美

 

风语者!平时喜欢研究各种技术,目前在从事后端开发工作,热爱生活、热爱工作。