快速排序在什么情况下最能发挥其长处

Question

如题所述

Answer 1

最好情况：

每一次划分对一个记录定位后，该记录的左侧子表与右侧子表的长度相同，为O(nlog2n)。

最坏情况：

每次划分只得到一个比上一次划分少一个记录的子序列（另一个子序列为空），为 O(n2)。

扩展资料

快速排序实现原理：

快速排序的基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

1、默认数组的第一个数为基准数据，赋值给key，即key=array[low]。

2、因为默认数组的第一个数为基准，所以从后面开始向前搜索（high–），找到第一个小于key的array[high]，就将 array[high] 赋给 array[low]，即 array[low] = array[high]。（循环条件是 array[high] >= key；结束时 array[high] < key）

3、此时从前面开始向后搜索（low++），找到第一个大于key的array[low]，就将 array[low] 赋给 array[high]，即 array[high] = array[low]。（循环条件是 array[low] <= key；结束时 array[low] > key）

4、循环 2-3 步骤，直到 low=high，该位置就是基准位置。

5、把基准数据赋给当前位置。

Answer 2

最好情况：
每一次划分对一个记录定位后，该记录的左侧子表与右侧子表的长度相同，为O(nlog2n)。
最坏情况：
每次划分只得到一个比上一次划分少一个记录的子序列（另一个子序列为空），为 O(n2)。本回答被网友采纳

Answer 3

被排序的数据中含有多个相同的排序关键字

Answer 4

？？？这是啥软件？EXCEL？问题描述不清。。。。追问

是数据结构里面的知知识

追答

好吧，这个我帮不了你了，数据库我懂的比较少