【觀念講解】 為什麼我們要費盡這麼多功，去排序一個數列？



大家辛苦了，學到這邊其實量也不少，這邊稍微喘口氣，看個文章整一整目前的概念：）



到這邊，我們已經學過以下排序法：

二元樹的資料結構，可以實作出：QuickSort、MergeSort

二元搜尋樹的資料結構，可以實作出：TreeSort



排序法、排序法，每個演算法書籍都有談到，卻很少有人詢問「為什麼要學排序」？

答案其實很簡單，只是我們要有意識地讓自己去理解，才能明白學這些的目的與根源。



Ans:「讓我們能使用 Binary Search」



使用二元收尋法的最大前提就是，你的陣列要是已經排序好的。

所以為了能使用二元收尋法，我們才要大費周章去將各種亂數陣列整理排序好！



方法一： 透過QuickSort、MergeSort將一個 [5,3,4,1,2] 整理成排序好的陣列 [1,2,3,4,5]，

我們就能將此陣列「看成」一顆以Array實作的「二元搜尋樹」，也就能進行二元搜尋法了 (＊本觀念將在下面單元詳細解說，很重要實用的一個單元！)



方法二： 直接將 [5,3,4,1,2] 一個一個放入，組成一顆以List實作的「二元搜尋樹」的資料結構，也就能進行二元搜尋法

而二元搜尋樹本身是一個資料結構，同時也是一種概念上「排序好的數列」，這在我們利用中序遍歷實作TreeSort時，已經明白展示，很有趣的一個觀念。



二元搜尋法聽起來很好，但它有什麼缺點呢？



Ans: 歪斜的二元搜尋樹反而效率極差 (n)



這個概念也是先前單元詳細介紹過，這邊特別再提出來，因為非常重要。

只有整理得好好的二元搜尋樹，才能發揮好的搜尋成效 (log・n )。



最後幫大家整出一個總結：

問題：為何要將數列排序？

目的：使用二元搜尋法

先決條件：數列已經排序好

方式：各種排序法

最佳結果：拿到log(n)的搜尋效率

最糟結果：歪斜的二元搜尋樹，只能有n的搜尋效率