插入排序

包括直接插入排序和希尔插入排序

直接插入排序

将一个记录插入到已经排序好的有序表中。

• 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方法排序时，必须采用稳定的排序算法
• 对于不稳定的算法，只要能举出一个实例说明即可
• 快速排序，希尔排序、堆排序是不稳定的排序，直接选择排序也是不稳定的。