Question

C++数据结构问题 2道 求大神解决

快速排序问题（quick sort）
原题：
explain why selecting the leftmost element as the pivot element is especially bad if the input is already sorted.
2.
原题：
how many comparisons are required to find the largest integer in an unsorted array.

• 你的回答被采纳后将获得：
• 系统奖励15（财富值+成长值）+难题奖励10（财富值+成长值）+提问者悬赏20（财富值+成长值）

Answer 1

1. 快速排序的原理是，每次将随机数组分成两部分，分组的依据是：选择一个元素(一般选择第一个元素)，设为A。然后扫描一遍数组，如果扫描到的元素比A小，则放在右边，扫描到的元素比A到则放在A的左边，最后以A为中心，把数组分成了两部分，这样一次递归就可以实现排序。而如果数组是已经排好序，那么此时弱选择第一个元素为基准元素，那么每次分组循环后，数组比并没有发生改变，相反还花费了很多比较的时间，所以时间效率是很差的。时间复杂度是O(N^2)；

2. 找到为排序数组中的最大元素的时间复杂度是O(N)，因为起码要扫描一遍数组，所以起码得比较n-1次。