最简单的选择算法是通过遍历列表找到最小(或最大)的元素,在此过程中跟踪当前的最小(或最大)值。这种算法与选择排序有关。相反地,最困难的选择算法是寻找中位数,这必然需要n/2的空间。 事实上,一个专门的中位选择算法可用来构造一个一般选择算法,例如中位数的中位数(英语:Median of medians)。已知最好的选择算法是快速选择(quickselect),它与快速排序有关。和快速排序类似,它有渐进最佳的复杂度,但是最坏情况的复杂度较差。不过这可以通过调整基准(pivot)的选择来优化。
This browser is not supported by Wikiwand :( Wikiwand requires a browser with modern capabilities in order to provide you with the best reading experience. Please download and use one of the following browsers:
Your input will affect cover photo selection, along with input from other users.
X
Get ready for Wikiwand 2.0 🎉! the new version arrives on September 1st! Don't want to wait?
Oh no, there's been an error
Please help us solve this error by emailing us at support@wikiwand.com
Let us know what you've done that caused this error, what browser you're using, and whether you have any special extensions/add-ons installed.
Thank you!