学习C++和C语言心得 8

三种线性排序(冒泡排序,选择排序,插入排序)

1.冒泡排序

把两个相邻的数进行比较，如图，如果左边的数比右边的数大，则把这两个数进行位置的调换或数的调换，把左边调换来的那个数，再跟与它相邻的右边的数进行比较，已经判断和调换，一直进行如上操作，每次循环数为上一次循环数减一，直到进行到最右边的数即可。

2.选择排序

选择排序首先要找到这组数列中的未知部分最小或者最大项，把最小项交换到如图最左边已知部分（或把最大项交换到最右端），这种排序要进行已知数组项数+1。

3.插入排序

插入排序把数组分为已排序区和未排序区。取未排序区的元素，在已排序区上找到一个合适的位置插上去。

4.三种排序的区别

（1）原理不同

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

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

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

（2）时间复杂度不同

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

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

（3）空间复杂度不同

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

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

（4）实现难度不同

插入排序相对简单，易于理解和实现；

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

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

（5）各自优缺点

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

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

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