快速選擇(Quickselect)演算法,快速尋找第 K 小或是第 K 大的元素
快速選擇(Quickselect)演算法是利用快速排序(Quick Sort)演算法,在排序序列的同時,選擇出序列中第 K 小或是第 K 大的元素。若我們只想要從序列中找出一個第 K 小或是第 K 大元素,使用快速選擇法會比使用快速排序法來得快很多,因為前者不需要把序列的排序完整做完,平均只需線性時間即可找到結果。
MagicLen · https://magiclen.org
本站也提供简体中文版。切换到简体中文版
標籤
共 1 篇文章
快速選擇(Quickselect)演算法是利用快速排序(Quick Sort)演算法,在排序序列的同時,選擇出序列中第 K 小或是第 K 大的元素。若我們只想要從序列中找出一個第 K 小或是第 K 大元素,使用快速選擇法會比使用快速排序法來得快很多,因為前者不需要把序列的排序完整做完,平均只需線性時間即可找到結果。