Quick Sort

• 特性
  1.Unstable
  2.In-place
  3.inaverage : O(nlogn)
  worse : O(n^2)

• 過程
  1.選定pivot，切成兩個序列
  2.把小的序列做sorting
  3.merge（直接並排即可）

• worse case
  如果每次選的pivot都選不好（如最小值），最會有最糟的情況

• partition algorithm

• How to pick pivot
  1.選最大或最小
  -->爛
  2.隨機挑
  3.先洗牌
  4.Midan of three
  因為我們想抓出中位數，但這樣會花太多時間
  --->拿最前、最後、中間三個，選三個之中的中位數

• 小技巧
  若N<20時，做insertion sort會比較快

• Summary

  | Algorithm | Time | Note | | :--- | :--- | :--- | | selection sort | O(n^2) | unstable, in-place, slow | | insertion sort, bubble sort | O(n^2) | stable, in-place, slow | | quick sort | O(nlogn) | unstable, in-place, fast | | heap sort | O(nlogn) | unstable, in-place, fast | | merge sort | O(nlogn) | stable, not in-place, fast |