kk匡的日記&學習筆記

穩定的排序

時間複雜度

空間複雜度

氣泡排序 Bubble sort

最差，平均都是O(n^2)，最好是O(n)

1

雞尾酒排序 Cocktail sort

最差，平均都是O(n^2)，最好是O(n)

1

插入排序 Insertion sort

最差，平均都是O(n^2)，最好是O(n)

1

歸並排序 Merge sort

最差，平均都是O(n log n)

O(n)

桶排序 Bucket sort

O(n)

O(k)

基數排序 Radix sort

O(dn)（d是常數）

O(n)

二叉樹排序 Binary search tree

O(n log n)

O(n)

圖書館排序Library sort

O(n log n)

(1+∞)n

不穩定的排序

時間複雜度

空間複雜度

選擇排序 Selection sort

最差，平均都是O(n^2)

1

希爾排序 Shell sort

O(n log n)

1

堆排序 Heapsort

最差，平均和最好情況都是O(n log n)

1

快速排序 Quicksort

平均是O(n log n)，最差是O(n^2)

O(log n)