试题详情
简答题若选择当前排序的第1个元素作为分界元素（也称枢轴或支点），什么情况下，快速排序法的时间效率会退化到简单排序法的程度？请说明理由。
  • 在待排序的原始序列中元素已经按值从小到大排好序的情况下，快速排序法的时间效率会变得很差，因为在排序过程中，每次选取的“分界元素”都是当前序列的最小值(最前那个元素)，经过一趟排序后，将原序列分解成为一个空序列和一个原序列长度仅减1的子序列，这样，对于长度为n的原始序列，必须经过n-1趟排序才能把所有元素定位，而且第i趟排序需要经过n-1次元素之间的比较才能为第i个元素定位，因此，总的排序时间达到O(n2)。

  • 关注下方微信公众号，在线模考后查看

热门试题