排序算法笔记

冒泡排序

算法介绍

冒泡排序是对于长度为 $n$ 的序列，重复执行 $n$ 次将 $a_i$ 与 $a_i$ $_+$ $_1$ ${\color{Gray} (1 \leqslant i \leqslant n-1)}$进行比较的算法。

时间复杂度

综上所述,冒泡排序的时间复杂度是$O(n^2)$。

动图

(与描述有细微差别)

选择排序

算法介绍

选择排序是对于长度为 $n$ 的序列，先固定好需要排序的数 $a_i$ 再寻找接下来 最小的数 $a_j$ 与 $a_i$ 对调 ${\color{Gray} (1 \leqslant i <j \leqslant n)}$ 的算法。

时间复杂度

综上所述,选择排序的时间复杂度是$O(n^2)$。

动图

插入排序

算法介绍

插入排序是对于长度为 $n$ 的序列，先取出需要排序的数 $a_i$ 再寻找适合其的间隙插入 ${\color{Gray} (1 \leqslant i \leqslant n)}$ 的算法。

时间复杂度

综上所述,插入排序的时间复杂度是$O(n^2)$。

动图

归并排序

算法介绍

归并排序是使用递归（分治）来实现的排序算法。归并排序对于长度为 $n$ 的序列，把序列对半分进行两次递归，直至 $n \leqslant 2$；若 $n \leqslant 2$ 则把序列进行排序；当递归程序返回时，则再把返回的数据进行排序。

时间复杂度

综上所述,归并排序的时间复杂度是$O(nlogn)$。

动图

快速排序

算法介绍

快速排序是使用递归（分治）来实现的排序算法。快速排序对于长度为 $n$ 的序列，先找一个基准数 $a_i$ ，把序列小于基准数的放在基准数前面，其余的放后面，一直递归基准数前面的序列，直至基准数前面的序列长度为1，接着再递归基准数后面的数。

时间复杂度

综上所述,快速排序的时间复杂度是$O(n^2)$。

动图

若有错误，欢迎指正

未经原作者许可不得转载

图源：网络，侵删