Bubble Sort
优点:
缺点:
(1) 慢,每次只能移动相邻两个数据.
(2) its O(n2) complexity means that its efficiency
decreases dramatically on lists of more than a small number of
elements.
(3)
Bubble sort also interacts poorly with modern CPU hardware. It requires
at least twice as many
writes as insertion sort, twice as many cache misses, and asymptotically more branch mispredictions. Experiments by Astrachan sorting strings in Java show bubble sort to be roughly 5 times slower than insertion sort and 40% slower than selection sort.
适用范围:
在计算机图形学中,在几乎排序好的数组,用于检测一些非常小的错误(例如仅仅交换两个元素),可以让其复杂度仅仅为线性(2n).例如,多边形填充算法.
复杂度:
Selection Sort
优点:
稳定.
swap的次数较少Θ(n).
缺点:
比较次数较多
适用范围:
(1)对于像merge
sort这类算法的优化.当元素比较少的时候,可以切换成selection sort or
insertion sort.\
(2)对于像EEPROM(Electrically Erasable Programmable Read-Only Memory)和Flash memory,write的代价比read的代价高的排序.
复杂度:
Insertion Sort
优点:
比较次数一般比selection sort少一半.
缺点:\
比较次数不一定,比较次数越少,插入点后的数据移动越多,特别是当数据总量庞大的时候,但用链表可以解决这个问题.
适用范围:
(1) write to the array O(n2) times.
(2) 对于像merge
sort这类算法的优化.当元素比较少的时候,可以切换成selection sort or
insertion sort.
复杂度:
Shell Sort
优点:
快,数据移动少.
缺点:
不稳定,d的取值是多少,应取多少个不同的值,都无法确切知道,只能凭经验来取.
适用范围:
复杂度:
Quick Sort
优点:
极快,数据移动少.
缺点:
不稳定
适用范围:
复杂度:
Bucket/Bin Sort
优点:
快,效率达到O(1).
缺点:
数据范围必须为正整数并且比较小.
适用范围:
复杂度:
Merge Sort
优点:稳定
缺点:
适用范围:用于像硬盘或磁带驱动器这类数据太大而无法装进内存中的数据.
复杂度:
Hash Table
AVL Tree
Red Black Tree
References: Wikipedia.