一、冒泡排序

冒泡

1、算法描述和具体实现

大致流程描述：

（1）比较相邻的元素。如果第一个比第二个大，就交换它们两个；

（2）每次遍历结束，能够找到该次遍历过的元素中的最大值

（3）如果还有没排序过的元素，继续（1）

代码实现：

冒泡排序

tips：一种原地排序算法，稳定排序算法。

有优化空间，主要从两方面进行优化：

①减少外层遍历次数

②让每次遍历能找到两个极值

平均时间复杂度：O(n^2)

空间复杂度： O(1)

稳定性：稳定

二、选择排序

找到数组中的最小（大）值，并将其放到第一位，然后找到第二小的值放到第二位……以此类推。

大致流程描述：

（1）取出未排序部分的第一个元素，遍历该元素之后的部分并比较大小。对于第一次遍历，就是取出第一个元素

（2）如果有更小的，与该元素交换位置

（3）每次遍历都能找出剩余元素中的最小值并放在已排序部分的最后

代码实现：

选择排序

tips：一种原地排序算法，不稳定排序算法。

平均时间复杂度：O(n^2)

空间复杂度： O(1)

稳定性：不稳定

三、插入排序

直接插入排序

它的基本思想是: 将待排序的元素按照大小顺序, 依次插入到一个已经排好序的数组之中, 直到所有的元素都插入进去.

大致流程：

（1）取未排序部分的第一个元素。第一次遍历时，将第一个元素作为已排序元素，从第二个元素开始取

（2）遍历前面的已排序元素，并与这个未排序元素比较大小，找到合适的位置插入

（3）继续执行（1）

代码实现：

插入排序

tips：一种原地排序算法，稳定排序算法。

平均时间复杂度：O(n^2)

空间复杂度： O(1)

稳定性：稳定