几种常见排序算法时间复杂度[通俗易懂]

​

大家好，我是架构君，一个会写代码吟诗的架构师。今天说一说几种常见排序算法时间复杂度[通俗易懂],希望能够帮助大家进步!!!

1、插入排序

插入排序时间复杂度：

最好：

所有元素已经排好序，只需遍历一遍，无需交换位置；

最坏：

所有元素逆序排列，遍历一次需要比较的元素个数每次+1，所以时间复杂度是O(n^2);

平均时间复杂度就是O(n^2)喽。

2、快速排序

有关快速排序时间复杂度：

最好的时间复杂度和平均时间复杂度就是O(nlogn);

正常情况下是递归log2n次，每次遍历的最坏时间复杂度是n，所以平均时间复杂度是O(nlogn)；

最好的时间复杂度就是每次都划分的很均匀；时间复杂度就是O(nlogn)；

最坏的时间复杂度是O(n^2),这种情况就是原先的数据就是排序好，这样每次只能位移一个数据，

每次划分的子序列只比上一次划分少一个记录，注意两一个为空。

3、归并排序

归并排序时间复杂度：

归并排序无论在什么情况下，将数组拆分都需要log(n)次；

在归并时，也需要遍历比较两个数组的大小，平均时间复杂度O(n)；

所以归并排序最好最坏时间复杂度都是nlogn;

空间复杂度是O(n)；

4、堆排序

堆排序每次都要将一个元素上升到堆顶，然后放回最后，需要n轮，固定不变

每一轮堆调整的时间复杂度是log(n),n依次递减

所以堆排序的时间复杂度是O(nlogn)