排序小结

选择排序

• Find smallest item.
• Swap this item to the front and ‘fix’ it.
• Repeat for unfixed items until all items are fixed.

堆排序

• Bottom-up heapify input array.
  • Sink nodes in reverse level order
• Repeat N times:
  • Delete largest item from the max heap, swapping root with last item in the heap.

归并排序

1. Split the items into half.
2. Mergesort each half.
3. Merge the two sorted halves to form the final result.

插入排序

Repeat for i = 0 to N - 1:

• 指定第 i 项为traveller
• 利用挨个swap将该项尽可能换到前面

希尔排序

插入排序的改进版本，用较大的步长来移动数据，再取越来越小的步长进行排序

1. 将待排序序列分为若干子序列（每个子序列的元素在原始数组中间距相同）；
2. 对这些子序列进行插入排序；
3. 减小每个子序列中元素之间的间距，重复上述过程直至间距减少为1

希尔增量序列(朴素的): $h_t = \lfloor N/2 \rfloor$ 和 $h_k = \lfloor h_{k+1} / 2 \rfloor$

快速排序

选取pivot, 分区(左边小于等于，右边大于等于)，然后递归

• 选取 pivot
  • 朴素方法：pivot = arr[0]（对于排好序的数组仍会消耗 O(N2) 的时间）
  • 安全方法：pivot = random element in arr （但随机数生成也有开销）
  • 三数中值分割法：pivot = (left + center + right) / 3
• 分割策略
  • Tony Hoare’s Partioning：两个指针分别位于数组的两端，彼此走向对方，交换不喜欢的元素直到两指针交错

桶排序

把排序的序列放到若干个有大小顺序的桶中，每个桶内再分别进行排序，最后再按桶的顺序将元素合并

• 适用于待排序数据值域较大但分布比较均匀的情况
• 用空间换时间

计数排序

计数每个元素出现的次数，然后迭代整个数组来放置元素。

基数排序

LSD Radix Sort：从低位到高位对每一位进行排序

稳定性

• 稳定排序：冒泡、归并、插入、基数、桶排
• 不稳定排序：快排、希尔、堆排、选择

Sorts

	Best Case Runtime	Worst Case Runtime	Space	Demo	Notes	Stable?
Selection Sort	$Θ(N^2)$	$Θ(N^2)$	Θ(1)	Link		No
Heapsort  (in place)	Θ(N)*	Θ(N log N)	Θ(1)**	Link	Bad cache (61C) performance.	No
Mergesort	Θ(N log N)	Θ(N log N)	Θ(N)	Link	Faster than heap sort.	Yes
Insertion Sort (in place)	Θ(N)	$Θ(N^2)$	Θ(1)	Link	Best for small N or almost sorted.	Yes
Ramdom Quicksort	Θ(N log N)	$Θ(N^2)$	Θ(log N) (call stack)	Link	Fastest sort	No
Counting Sort	Θ(N+R)	Θ(N+R)	Θ(N+R)	Link	Alphabet keys only	Yes
LSD Sort	Θ(WN+WR)	Θ(WN+WR)	Θ(N+R)		Strings of alphabetical keys only	Yes
MSD Sort	Θ(N+R)	Θ(WN+WR)	Θ(N+WR)		Bad caching(61C)	Yes

*: An array of all duplicates yields linear runtime for heapsort.<\br> **: Assumes heap operations implemented iteratively, not recursively <\br> ***: Assumes constant compareTo time

N: Number of keys， R: Size of alphabet，W: Width of longest key.