插入排序

从数组第二个元素开始循环，比较其之前的元素有无比它大的，若有则往后移，最后将这个值放到正确位置
时间复杂度O（n^2）

合并排序（归并排序）

合并排序：

合并操作：

时间复杂度O（nlgn）

快速排序

采用分治策略

排序一个数组A的全部元素，初始调用为QUICKSORT（A，1，A.length）

x为主元，并围绕x来分割A为两个数组
函数中，p为比x小的子数组的初始索引，i为比x小的子数组的最后索引，j为遍历除了x的数组元素的主索引

示例：

最坏情况

发生在分割中心选择了最大或最小的元素
此时为O（n^2）

最好情况

分割中心每次都选到中值元素
此时为O(nlgn)

平均情况

时间复杂度和最好情况相同

计数排序

n为A中元素数目，k为A中种类数目

3-4行：将索引为A[j]的C数组元素+1，表示此索引表示的值在A数组中出现的次数
5-6行：将C[i]表示成小于等于i的元素的个数
9-11行：j从n开始直到1，将A[j]值赋给索引为A[j]出现次数的B数组中，然后相应出现次数减1

示例

将A数组中出现的元素的次数记录在C数组中，
C数组中元素为小于等于此索引的A中元素出现的次数
最后将其表现为B数组，就排好序了

时间复杂度为O（n+k）
小范围整数排序O（n）
排序结果具有稳定性：对于相同值的元素，在原来数组中的先后顺序排序后得以保留

基数排序

按照数字的基底一位位地排序
基底：如十进制数基底为10，二进制数为2
基底表示如下：

基数排序从低位开始进行稳定的增序排序，一直到最大位为止

桶排序

示例1

将A数组的元素插入到B中

对B中每一个链进行插入排序（总之排序就对了）

示例2

平均情况下，时间复杂度为O（n）
因为数据是均匀、独立地分布在[0，1）之间，所以一般不会出现很多数落在同一个桶的情况。