快速選擇算法主要用于在一個(gè)未排序的數(shù)組中尋找第k個(gè)最小/最大的數(shù)。它的方法類似于快速排序，快速排序和快速選擇算法都是Tony Hoare發(fā)明的。

快速選擇算法思路

只需要每次判斷k在左區(qū)間還是右區(qū)間，一直遞歸查找k所在的區(qū)間。

當(dāng)只剩下一個(gè)數(shù)時(shí)，數(shù)組中就只有一個(gè)數(shù)，答案是返回?cái)?shù)組的值。

平均時(shí)間復(fù)雜度O(n)，不過(guò)最壞情況仍然是O(n^2)

Top K問題

找到未排序的數(shù)組中第k個(gè)最大的元素。（數(shù)組排序后找到第k個(gè)最大的元素，而不是第k個(gè)不同的元素。）

快速選擇算法的過(guò)程

這里求的是從小到大排序后的第?k?個(gè)數(shù)

1.找到分界點(diǎn)x（諸如q[L]，q[(L+R)/2]，q[R]都行）

2.使左邊所有數(shù)L<=X,右邊所有數(shù)R>=X（和X相等的數(shù)在左右兩邊都有可能）

3.遞歸判斷k在左右邊，當(dāng)要求的第k個(gè)數(shù),k<=j + 1，則遞歸排序左邊，否則遞歸排序右邊。

愉悅，今天的學(xué)習(xí)很快樂！

夕弦的圖片由NovelAI生成，使用的模型以u(píng)p主紅心咖啡_Official的八舞模型為基底，并做了一定的更改訓(xùn)練?