[算法] 算法课笔记-排序

排序算法分类

• 就地排序（inplace）：排序算法所需辅助空间不依赖于元素个数N
• 稳定排序（stable）：同键值的元素在排序后原相对顺序不变

排序算法对比

|排序算法|就地
排序|稳定
排序|最差时间
复杂度|平均时间
复杂度|最佳时间
复杂度|备注 |—– |选择排序（selection）|是||C=N²/2|C=N²/2
M=N|C=N²/2|C比较 M移动 |冒泡排序（Bubble）|是|是|C=N²/2|C=N²/2|C=N|当N较小或部分已排序时使用 |插入排序（insertion）|是|是|C=N²/2|C=N²/4
M=N²/4|C=N|当N较小或部分已排序时使用（部分已排序时，插入排序比选择排序要快） |希尔排序（shell）|是||?|?|C=N|严谨代码，次二次时间 |归并排序（merge）||是|C=NlgN|C=NlgN|C=NlgN|NlgN保证，稳定
Java中对对象排序
Perl, C++ stable sort, Python stable sort, Firefox JavaScript,… |快速排序（quick）|是||C=N²/2|C=2NlnN|C=NlgN|NlgN概率保证，实践中最快
Java中对原始数据类型排序
C qsort, Unix, Visual C++, Python, Matlab, Chrome JavaScript,… |三路基数快速排序
（3-way quick）|是||C=N²/2|C=2NlnN|C=N|当存在重复键值时改善快速排序 |堆排序（heap）|是||C=2NlgN|C=2NlgN|C=NlgN|NlgN保证，就地

选择排序

插入排序

希尔排序

Knuth Shuffle

合并排序

快速排序

快选

三路基数快速排序

堆排序