大家好,我是架构君,一个会写代码吟诗的架构师。今天说一说几种常见排序算法时间复杂度[通俗易懂],希望能够帮助大家进步!!!
插入排序时间复杂度:
最好:
所有元素已经排好序,只需遍历一遍,无需交换位置;
最坏:
所有元素逆序排列,遍历一次需要比较的元素个数每次+1,所以时间复杂度是O(n^2);
平均时间复杂度就是O(n^2)喽。
有关快速排序时间复杂度:
最好的时间复杂度和平均时间复杂度就是O(nlogn);
正常情况下是递归log2n次,每次遍历的最坏时间复杂度是n,所以平均时间复杂度是O(nlogn);
最好的时间复杂度就是每次都划分的很均匀;时间复杂度就是O(nlogn);
最坏的时间复杂度是O(n^2),这种情况就是原先的数据就是排序好,这样每次只能位移一个数据,
每次划分的子序列只比上一次划分少一个记录,注意两一个为空。
归并排序时间复杂度:
归并排序无论在什么情况下,将数组拆分都需要log(n)次;
在归并时,也需要遍历比较两个数组的大小,平均时间复杂度O(n);
所以归并排序最好最坏时间复杂度都是nlogn;
空间复杂度是O(n);
堆排序每次都要将一个元素上升到堆顶,然后放回最后,需要n轮,固定不变
每一轮堆调整的时间复杂度是log(n),n依次递减
所以堆排序的时间复杂度是O(nlogn)