学习笔记之排序
[学习笔记] - 排序
排序
稳定性
假定\(k_i\)==\(k_j\) , 排序前\(r_i\)在\(r_j\)前面, 排序后\(r_i\)仍旧在\(r_j\)前面，那么称为排序方法是稳定的；否则是不稳定的。
内排序 VS 外排序
- 待排序所有记录全部在内存中- 内排序。（以下均为内排序）
- 如果记录太多，无法同时全部放在内存，需要内存和外部存储交互数据 - 外排序
排序的分类
按借助的主要操作，分为：
- 插入排序
- 交换排序
- 选择排序
- 归并排序
按复杂度， 分为：
简单算法
改进型算法
冒泡排序、简单选择排序、插入排序 属于简单算法
希尔排序、堆排序、归并排序、快速排序 属于改进算法
排序算法
冒泡排序
选择排序
查看 Post not found: 简单选择排序 选择排序
直接插入排序
查看 Post not found: 直接插入排序 直接插入排序
希尔排序
堆排序
归并排序
快速排序
总结
- 简单算法： 冒泡，选择，直接插入
- 改进算法： 希尔， 堆，归并，快速
堆、归并、快速总体优于希尔排序，并且远远胜于简单排序算法。
从最好情况看， 反而冒泡和直接插入时间复杂度更小，因此如果待排序列基本有序，可以考虑冒泡和直接插入算法。
从最坏情况，堆排序和归并排序强于快速排序。
综合来看经过优化的快速排序是性能最好的排序算法。
摘录： 大话数据结构- 9.排序
