排序

排序的基础操作

比较和交换

比较的话可以使用java的comparable接口

交换一般都是互换位置

排序的基本类型

是否原地 关系着需不需要额外的物理空间

是否稳定 意味着相同的元素排序前后的位置是否有变动

简单排序类型

简单排序.jpg

1. 希尔排序是对插入排序的一种优化

2. 插入排序只关注左边的数组

3. 选择排序只关注右边的数组

基于分治思想和递归方法的排序类型

归并排序和快速排序.jpg

java的数组排序方法会根据数组的实际长度和实际有序性来适当的选择不同的排序方法，以保证在大多数情况下都能获取到稳定的性能。

插入排序-》快速排序-》归并排序

优先队列的实现-堆排序

堆的数据结构是平衡的二叉树。

分别有上浮操作和下沉操作

参考《算法》