Lucy's Note of Coding

完滿(Full)二元樹vs 完全(Complete)二元樹vs 完美(Perfect)二元樹

圖片來源：https://blog.csdn.net/weixin_44441009/article/details/115333213

  // 進行FibonacciSearch前提，先準備好有序陣列
  // 透過斐波那契數列取得變動的中間索引
  // f[k]會配合待排序陣列之長度

  // 進行InterpolationSeach前提，先準備好有序陣列
  // 優勢：適合用於陣列值為較連續的、值的差距不大、資料量大
  // 唯有取得中間值公式與二分搜尋不同，剩餘作法一致

需要二維陣列：第一維用來表示第幾個桶，第二維用來儲存符合x位數基數的值
需要一維陣列：用來表示二維陣列的每個桶，儲存幾個值
每個桶的空間：以待排序陣列長度為基準
步驟：1. 先找出最大值，並得出最大值位數 => 基數排序進行的次數，假設最大值為百位數，那基數排序會排序3次
2. 求出個位數基數，將值依序放入二維陣列中
3. 紀錄每個桶放入幾個數 => 入一維陣列
4. 取出二維陣列的值放回原待排序陣列，並清空二維陣列、一維陣列做為下一次排序使用

合併排序：空間換時間

快速排序(QuickSort)
 

希爾排序(ShellSort)

插入排序(InsertionSort)：小到大