冒泡排序 （稳定排序）

常见的排序算法 冒泡排序 冒泡排序

在内循环中，第i次排序已经将最大放在最后，所以不用在进行排序。只要对length - i - 1 进行排序就可以。

冒泡排序复杂度

插入排序 （稳定排序）

插入排序和冒泡排序的比较

插入排序的思想是不断把没有排好序的数，插入到排好的部分。

插入排序

外循环：从头遍历数组，并保存当前的值
内循环：从当前值的坐标向前遍历，如果比该数大就向后移动数组中的数，如果小就把当前值保存下来。
返回

复杂度分析

归并排序 （稳定排序）

归并排序 归并排序 归并排序中的Merge 合并排序

思想：

• 如果左边的坐标大于右边的坐标，返回
• 计算中间坐标，对左边排序，对右边排序，然后Merge

Merge思想：
因为左边和右边的数组都排好序了

• 如果左边都遍历完了，就直接复制右边的数组
• 如果右边的遍历完了，就直接复制左边的数组
• 比较左边和右边的数组，分别对左右进行比较和坐标递增

归并排序复杂度

快速排序

快速排序 快速排序 Screen Shot 2019-07-12 at 10.40.05 am.png

算法思想：

• 选一个点，使左边的都比这个点小，右边的都比这个点大
• 递归的对左右进行排序

其中对partition思想：

• 随机选一个数，放到最右边
• 遍历数组，当比选定的值小的时候就交换放到i左边
• 最后i的值就是选定的值
• 返回i

快速排序复杂度 快速排序 快速排序空间复杂度

拓扑排序

拓扑排序 拓扑排序 计算过程

算法思想：

• 删除入度为0的点，并删除边
• 更新每个点的入度
• 循环直到没有点为止

排序过程 时间复杂度