数据结构-排序法

排序好处：

• 数据较容易阅读
• 数据较利于统计及整理
• 可大幅度减少数据搜索时间

按执行时内存分类

• 内部排序：排序的数据量小，完全可以在内存内进行排序
  
  • 冒泡排序法、选择排序法、插入排序法、合并排序法、快速排序法、堆积排序法、希尔排序法、基数排序法
    
• 外部排序：排序的数据量无法直接在内存内进行排序，而必须使用辅助存储器（硬盘）
  • 直接合并排序法、K 路合并法、多相合并法

排序算法分析

• 算法是否稳定
  • 稳定排序是指数据在经过排序后，两个相同键值的记录仍然保持原来的顺序
  • 原始数据：7_(左)、2、9、7_(右)、6
  • 稳定排序：2、6、7_(左)、7_(右)、9
  • 不稳定排序：2、6、7_(右)、7_(左)、9
• 时间复杂度(省略系数、低阶、常量)
  • 最好情况(Best Case)：数据已完成排序
  • 最坏情况(Worst Case)：每一键值都需重新排列
  • 平均情况(Average Case)：所有情况次数/所有情况数量
• 空间复杂度
  • 算法在执行过程中所需付出的额外内存空间，仅用到一个额外的空间，空间复杂度最好

 

内部排序法

	排序名称	排序特性
简单排序法	冒泡排序法（Bubble Sort）	稳定排序空间 复杂度为最佳，只需一个额外空间 O(1)
	选择排序法（Selection Sort）	不稳定排序 空间复杂度为最佳，只需一个额外空间 O(1)
	插入排序法（Insertion Sort）	稳定排序 空间复杂度为最佳，只需一个额外空间 O(1)
	希尔排序法（Shell Sort）	不稳定排序 空间复杂度为最佳，只需一个额外空间 O(1)
高级排序法	快速排序法（Quick Sort）	不稳定排序 空间复杂度最差为 O(n)，最佳为 O(log2n)
	堆积排序法（Heap Sort）	不稳定排序 空间复杂度为最佳，只需一个额外空间 O(1)
	基数排序法（Radix Sort）	稳定排序 空间复杂度为 O(np)，n 为原始数据的个数，p 为基底