快速排序最坏情况 [英] Quick sort Worst case

问题描述

我的工作只需要在下面的程序更好地理解它。

I am working on the program just needed in the following to understand it better.

什么是运行时间的快速排序，什么都可能导致更糟糕的情况下，表现最糟糕的情况？我们要如何快速排序程序miggate这个问题？

What is the worst case running time for Quicksort and what may cause this worse case performance? How can we modify quicksort program to miggate this problem?

我知道它有最坏的情况下为O（n ^ 2），我知道它发生在支点独特的最小或最大的元素。我的问题是我怎么能修改程序来缓解这个问题。

I know that it has worst case O(n^2) and i know it occurs when the pivot unique minimum or maximum element. My question is how can I modify the program to mitigate this problem.

一个很好的算法将是不错的。

A good algorithm will be good.

感谢

推荐答案

快速排序的性能取决于你的支点选择算法。最天真的支点选择算法是只选择第一个元素作为支点。很容易看出，这导致最坏情况下的行为，如果你的数据已经排序（第一个元素永远是分）。

Quicksort's performance is dependent on your pivot selection algorithm. The most naive pivot selection algorithm is to just choose the first element as your pivot. It's easy to see that this results in worst case behavior if your data is already sorted (the first element will always be the min).

有两种常见的算法来解决这个问题：随机选择一个支点，或选择三个位数。随机是显而易见的，所以我不会细讲。三个位数涉及选择三个元素（通常是第一个，中间的和最后一个），选择那些为支点的中值

There are two common algorithms to solve this problem: randomly choose a pivot, or choose the median of three. Random is obvious so I won't go into detail. Median of three involves selecting three elements (usually the first, middle and last) and choosing the median of those as the pivot.

由于随机数发生器通常是伪随机（因此确定性）和非随机位数三种算法是确定性的，这是可能的构造数据，其导致最坏情况下的行为，但是也很少为它来在正常用法。

Since random number generators are typically pseudo-random (therefore deterministic) and a non-random median of three algorithm is deterministic, it's possible to construct data that results in worst case behavior, however it's rare for it to come up in normal usage.

您还需要考虑对性能的影响。您的随机数发生器的运行时间会影响你的快速排序的运行时间。有三个的位数，则在增加的比较的数量。

You also need to consider the performance impact. The running time of your random number generator will affect the running time of your quicksort. With median of three, you are increasing the number of comparisons.

这篇关于快速排序最坏情况的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！