时间复杂度最坏是(nlogn)
时间复杂度均摊是(nlogn)
排序是不稳定的
快速排序是一种交换排序。
大致过程:利用分治的思想,将原数列分成两部分,使得左边的元素都小于基准值,右边的元素都大于基准值。分别对左右两边进行递归,直至数列只有一个元素,最后得到的总数列即是有序的。
时间复杂度分析:
由于每次递归都将数列分为两部分,故每次时间复杂度都为log2n,共有n个元素。在这种情况下,时间复杂度为O(nlog2n)。当数列中的元素全部有序时,快排时间复杂度达到最高O(n^2)。所以它的平均时间复杂度为O(nlog2n)
快排是一种不稳定的排序算法。
B
BC
这道题你会答吗?花几分钟告诉大家答案吧!
扫描二维码,关注牛客网
下载牛客APP,随时随地刷题