資料結構&演算法筆記
  • Introduction
  • 1. Data Structure
  • 1.1 Stack
  • 1.1.1 Stack: Revert String
  • 1.1.2 Stack: Brackets Matching
  • 1.1.3 Stack: Reverse Polish Notation
  • 1.1.4 Stack: Calculattion for Reverse Polish Notation
  • 1.2 Queue
  • 1.2.1 Priority Queue
  • 1.3 Linked List
  • 1.3.1 Linked List - Reorder Function
  • 1.3.2 Ordered Linked List
  • 1.4 Tree
  • 1.4.1 Binary Search Tree
  • 1.4.2 Heap Tree
  • 1.4.3 Red-Black Tree
  • 1.4.3.1 RB Tree Insertion
  • 1.4.3.2 RB Tree Insertion Implementation
  • 1.4.3.3 RB Tree Delete
  • 1.4.3.4 RB Tree Delete Implementation
  • 1.4.4 B-Tree
  • 2. Algorithm
  • 2.1 Sort
  • 2.1.1 Bubble Sort
  • 2.1.2 Selection Sort
  • 2.1.3 Insertion Sort
  • 2.1.4 Merge Sort
  • 2.1.5 Quick Sort
  • 2.1.6 Merge Sort v.s. Quick Sort
  • 2.2 Search
  • 2.2.1 Binary Search
  • 2.3 Dynamic Programming
  • 2.3.1 Fibonacci Series
  • 2.3.2 Find Longest Common Suffix
  • X. Time Complexity Cheat Sheet
Powered by GitBook
On this page

Was this helpful?

2.1.6 Merge Sort v.s. Quick Sort

Previous2.1.5 Quick SortNext2.2 Search

Last updated 5 years ago

Was this helpful?

  • 兩者其實非常相似, 都是把資料分成兩邊, 直到不能再分了, 才把資料合起來. 不過quick sort最大的特色就是會有partition的這個動作, 講白了就是把數字分好大小後再繼續往下分, 所以這樣循環下去分到最小後, 也表示完成了排序的動作了.

  • 在大部分的worst case下, merge sort是優於quick sort的, 再加上merge sort的worst case跟quick sort的best case之時間複雜度是一樣的, 這樣看來似乎是merge sort比較快(理論上).

  • 可是實際上來說, 如果兩者都用遞迴的方式去實作的話, quick sort的method call為N, 那merge sort就會是2N-1(註1), 即merge sort多花了一倍的method call. 如果用迴圈來做, merge sort會花比較多時間在記憶體上面, 因為它不是in-place sorting.

  • 不過merge sort有一個很好的特性: 它是穩定的(stable sorting), 穩定的意思是說, 排序前與排序後, 擁有相同key值的兩個資料, 彼此之間的順序是一樣的.

  • 最後, 這兩者都是Divide and Conquer的做法, 只是quick sort為先苦後樂(遞迴之前的partition比較麻煩, 遞迴完後就沒事了); 而merge sort是先樂後苦(進入遞迴之前都沒事, 但是遞迴之後的合併動作就累了).

註1: 參閱, 注意merge function的step1~step2, 這是第一次的N, 即排序當前分割後的結果, 而step3, 把排序好的結果放回原本的array, 也會有一次N.

原始碼