在冒泡排序,插入排序,选择排序,快速排序中,在最最坏情况下,快速排序的时间复杂为O(n2) ,插入排序O(n2),选择排序O(n2),冒泡排序O(n2)。所以ABCD时间复杂度是一样的。
在快速排序算法中,最为关键的就是选取一个基值,将数组分为大于基值以及小于基值两部分,并返回基值所以在位置以利用于递归划分。
对数组a,设需要划分的其中一段为a[p]~a[r],我们期待的结果是得到一个q,其中p<=q<=r,使得a[p]~a[q-1]<=a[q]<=a[q+1]~a[r],这个时候原先的一段数组被分成了三部分。
首先,设基值为这段数组的最后一个元素a[r],我们希望最后得到的结果是a[r]现在对应的值在算法结束后可以排在比他大和小的两部分的中间爱。
然后令i=p-1; j=p,当发现有a[j]>x时,j继续前进,不需要任何移动。当发现a[j]<=x时,我们需要将这个元素放到小于基值的一边,于是将i自加1,并交换此时a[i],与a[j]的元素,然后j自加1。这个时候i指向的是比基值小的那段数据的最后一个元素,j指向的是第一个还没有判断的剩余元素。
上面一步不断循环直到j指向了r,此时只剩下r没有和基值判断了,而a[r]本来就是基值,而除了a[r]以外,a[p]~a[i]是小于基值的部分,a[i+1]~a[r-1]是大于基值的部分,所以此时只需交换a[i+1]和a[r]即可。
由于对数组a从头到尾扫描一次就可以得到结果,因此这一部分算法复杂度为o(n)
O(n log n)是什么?明天嘉兴市竞赛!!!!!!!!!!!!!
排一下序 好吗?
这个就是时间复杂度 比O(n^2)要低
本回答被提问者和网友采纳