插入排序
包括直接插入排序和希尔插入排序
直接插入排序
将一个记录插入到已经排序好的有序表中。
- sorted数组的第0个位置没有放数据
- 从sorted第二个数据开始处理：
如果数据比它前面的数据要小，说明数据需要往前移动。
a、首先将数据备份放到sorted的第0位置当哨兵
b、然后将该数据前面的那个数据后移
c、然后往前搜，找到插入的位置
d、找到插入位置之后，将第0位置的那个数据插入对应的位置。
O（n*n),当待排序记录序列为正序时，时间复杂度提高至O(n)。
希尔排序
先将整个待排序列分割成若干个子序列分别进行直接插入排序，待整个序列中的记录基本有序时，再对整体进行一次直接插入排序。时间复杂度O(n*n)。
交换排序
包括冒泡排序和快速排序
冒泡排序
这个算法的核心思想是扫描数据清单，寻找出现乱序的两个相邻项目，当找到这两个项目后，交换项目的位置后继续扫描，重复上面的操作直到所有项目都按顺序排好。该算法是专门针对已部分排序的数据进行排序的算法。
快速排序
通过一趟排序，将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分的关键小，则可分别对两部分进行继续的排序。
选择排序
分为直接选择排序和堆排序
直接选择排序
第i次选取i到length-1中间最小的值放在i位置。
堆排序
首先，数组里面用层次遍历的顺序放一颗完全二叉树。从最后一个非终端结点往前调整，直到到达根节点。
归并排序
将两个或两个以上的有序表组合成一个新的有序表。归并排序需要使用一个辅助数组，大小跟原数组相同，递归做法。每次都将目标序列分解成两个序列，分别排序两个子序列之后，再将两个排序好的子序列merge到一起。
基数排序
使用10个辅助队列，假设最大数的数字位数为x，则一共做x次，从各位数开始往前，第i为数字的大小为依据，将数据放进辅助队列，搞定之后回收。下次再以高一位开始的数字位为依据。
总结
所需辅助空间最多：归并排序
所需辅助空间最少：堆排序
平均速度最快：快速排序
不稳定：快速排序，希尔排序、堆排序
选择排序算法依据：
- 数据的规模
- 数据的类型
- 数据已有的顺序
按平均的时间性能来分： - 时间复杂度为O(nlogn)的方法有：快速排序、堆排序和归并排序，其中以快速排序最好
- 时间复杂度为O(n*n)的方法有：直接插入排序、冒泡排序和简单选择排序，其中以直接插入排序最好，特别是对那些关键字近似有序的记录效果更好
- 时间复杂度为O(n)的排序方法只有基数排序。
按平均的空间性能来分（指的是排序过程中所需要的辅助空间的大小）： - 所有的简单排序方法（包括：直接插入排序、冒泡排序和简单选择）和堆排序的空间复杂度为O(1)
- 快速排序为O(logn)，为栈所需的辅助空间
- 归并排序所需辅助空间最多，其空间复杂度为O(n)
- 链式基数排序需附设首尾指针，则空间复杂度为O(rd)
排序算法的稳定性能： - 稳定的排序算法是指，对于两个相等的关键字，它们在序列中的相对位置，在排序前和排序后没有改变
- 当多对关键字的记录顺序进行LSD方法排序时，必须采用稳定的排序算法
- 对于不稳定的算法，只要能举出一个实例说明即可
- 快速排序，希尔排序、堆排序是不稳定的排序，直接选择排序也是不稳定的。
