快速排序法在初始数据为正序时的时间复杂度能达到最好说法对吗?
1个回答
关注
![]()
展开全部
咨询记录 · 回答于2022-06-27
快速排序法在初始数据为正序时的时间复杂度能达到最好说法对吗?
要排序的数据已基本有序的情况下。快速排序的基本思想是以基准元素为中心，将待排序表分成两个子表，然后继续对子表进行划分，直到所有子表的长度为1。快速排序第一趟的结果是：将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小。快速排序法性能分析：快速排序的一次划分算法从两头交替搜索，直到low和high重合，因此其时间复杂度是O(n)；而整个快速排序算法的时间复杂度与划分的趟数有关。理想的情况是，每次划分所选择的中间数恰好将当前序列几乎等分，经过log2n趟划分，便可得到长度为1的子表。这样，整个算法的时间复杂度为O(nlog2n)。得出来是不对的
已赞过
评论
收起
你对这个回答的评价是？