数组

大致详见my-springboot项目

数组内存结构

数组存放在堆中

排序算法

评价指标

（1）时间复杂度：分析关键字的比较次数和记录的移动次数
（2）空间复杂度：分许排序算法中需要多少辅助内存
（3）稳定性：若两个记录A和B的关键字值相等，但排序后A、B的先后次序保持不变，则称这种排序算法是稳定的

分类

内部排序：整个排序过程不需要借助于外部存储器（磁盘等），所有排序操作都在内存中完成
外部排序：参与排序的数据非常多，数据量非常大。计算机无法把整个排序过程放在内存中完成，必须借助于外部存储器（磁盘等）。外部排序最常见的是多路归并排序。可以认为外部排序是由多次内部排序组成。

十大内部排序算法

（1）选择排序：直接选择排序、堆排序
（2）交换排序：冒泡排序、快速排序
（3）插入排序：直接插入排序、折半插入排序、Shell排序
（4）归并排序
（5）桶式排序
（6）基数排序

算法的5大特征

输入: 有0个或多个输入数据买这些输入必须有清楚的描述和定义
输出: 至少有一个或多个输出结果，不可以没有输出结果
有穷性: 算法在有限的步骤之后会自动结束而不会无限循环，并且每个步骤可以在可接受的时间内完成
确定性: 算法中的每一步都有确定的含义，不会出现二义性
可行性: 算法的每一步都是清楚且可行的，能让用户用纸笔计算

性能比较

平均时间
快速排序最佳。但在最坏情况下时间性能不如堆排序和归并排序
算法简单性
直接选择排序、直接插入排序、冒泡排序被认为是简单算法。Shell排序、堆排序、快速排序、归并排序被认为是复杂算法
稳定性
直接插入排序、冒泡排序、归并排序是稳定的；直接选择排序、快速排序、Shell排序和堆排序被认为是不稳定排序
待排序的记录数n的大小
n较小，宜采用简单排序；n较大宜采用改进排序

排序算法的选择