数据结构

1. 插入排序

   1. 直接插入排序
   2. 折半插入排序
   3. 希尔排序

2. 交换排序

   1. 冒泡排序
   2. 快速排序

3. 二路归并排序

4. 基数排序

5. 外部排序

   1. 多路平衡归并与败者树
   2. 置换-选择排序
   3. 最佳归并树

6. 排序算法的分析和应用

   算法		时间复杂度
   	最好情况	平均情况	最坏情况	空间复杂度	稳定性
   直接插入排序	$O(n)$	$O(n^2)$	$O(n^2)$	$O(1)$	是
   冒泡排序	$O(n)$	$O(n^2)$	$O(n^2)$	$O(1)$	是
   简单选择排序	$O(n^2)$	$O(n^2)$	$O(n^2)$	$O(1)$	否
   希尔排序				$O(1)$	否
   快速排序	$O(n\log n)$	$O(n\log n)$	$O(n^2)$	$O(\log n)$	否
   堆排序	$O(n\log n)$	$O(n\log n)$	$O(n\log n)$	$O(1)$	否
   二路归并排序	$O(n\log n)$	$O(n\log n)$	$O(n\log n)$	$O(n)$	是
   基数排序	$O(d(n+r)$	$O(d(n+r))$	$O(d(n+r)$	$O(1)$	是