快速選擇(Quickselect)演算法,快速尋找第K小的元素

快速選擇(Quickselect)是一種選擇元素的演算法,它可以快速地在一個未排序的資料中選擇出第K小的元素。它的作法如同快速排序法(Quick Sort)一樣,只是演算法結束的條件不同而已。快速選擇演算法的最佳與平均時間複雜度為O(n),最差的時間複雜度與快速排序法一樣均為O(n2)。

有關於快速排序法的介紹與說明可以參考這篇文章:

https://magiclen.org/sorting-algorithm/

快速選擇法的概念

先在陣列中找出一個pivot(支點、中心點),想辦法將比pivot小的元素移動到pivot的左邊,比pivot大的元素移動到pivot的右邊,由於pivot在完成移動之後的位置就已經固定了,先假設pivot在完成移動後的位置為p,所以如果當k等於p的時候,我們要找的第K小的元素就是pivot元素,但如果k小於p或是k大於p,就得再用同樣的方法繼續對pivot所在的p位置之左邊子陣列或右邊子陣列進行排序

由於快速選擇法並沒有完成所有的快速排序法的動作,不會將陣列完整排序完成,但也因此會有比較快的執行速度。

在介紹快速排序法的文章中,移動比pivot小的元素和比pivot大的元素的作法是同時從左右兩側開始,然而,其實也可以從其中一端開始就好,但前者的作法效能通常會好一點,因為搬移元素的次數比較少。為了讓讀者們可以自己練習去使用前者的方式來實作快速選擇法,因此在這篇文章的快速選擇法實作中,會使用後者,也就是一端移動的方式來完成。

快速選擇法的過程

假設現在有個陣列資料,內容如下:

要如何找到第2大的元素呢?

一開始,將陣列最右端(最尾端)的位置與元素定為pivot,並把陣列最左端(最前端)預設為pivot最後的移動位置,如下表所示:

接著從最左端開始,尋找比pivot元素還要小的元素。索引0的69就是了,如下表所示:

接著將pivot預計最後的移動位置與索引0交換(這兩個位置一樣,也可以不用換),然後再將pivot預計最後的移動位置往右位移,並繼續尋找比pivot元素還要小的元素,如下表所示:

找到索引2的30,如下表所示:

接著將pivot預計最後的移動位置與索引2交換,然後再將pivot預計最後的移動位置往右位移,並繼續尋找比pivot元素還要小的元素,如下表所示:

找到索引3的38,如下表所示:

接著將pivot預計最後的移動位置與索引3交換,然後再將pivot預計最後的移動位置往右位移,並繼續尋找比pivot元素還要小的元素,如下表所示:

如此類推,當找到索引8的32時,如下表所示:

接著將pivot預計最後的移動位置與索引8交換,然後再將pivot預計最後的移動位置往右位移,並繼續尋找比pivot元素還要小的元素,如下表所示:

此時已經尋找到除了pivot的尾端,可以確定pivot最後的移動位置了,接著將pivot移動至找到的位置,如下表所示:

移動之後的pivot所在位置,其左邊元素皆小於等於pivot,右邊的元素皆大於等於pivot。由於我們要找第2大的元素,就是陣列在排序之後索引8的位置,剛好就是pivot最後的移動位置,所以「79」是第2大的元素。若我們要找第2小的元素,也就是索引1的位置,則必須再對pivot左邊的子陣列繼續進行以上步驟。

快速選擇法的程式實作

快速選擇法的優化

當以上的快速排序法實作要處理一個反序的資料,將會有最差的時間複雜度,為了讓最差的時間複雜度不容易發生,可以將pivot的挑選改成隨機的方式進行。且為了減少搬移元素的次數,應使用快速排序法的文章中,同時從左右兩側開始移動比pivot小的元素和比pivot大的元素的作法會比較好。優化過的快速選擇法之實作程式,可以參考MagicSortMagicSort是一個Java函式庫,完整實作並應用了多個排序演算法,有興趣者可以參考這篇文章:

https://magiclen.org/magicsort/

關於作者

Magic Len

各位好,我是Magic Len,是這網站的管理員。我是台灣台中大肚山上人,畢業於台中高工資訊科和台灣科技大學資訊工程系,曾在桃機航警局服役。我熱愛自然也熱愛科學,喜歡和別人分享自己的知識與經驗。如果你有興趣認識我,可以加我的Facebook,並且請註明是從MagicLen來的。

相關文章