快速排序
实现步骤：
1：从数列中挑出一个元素，称为 “基准”（pivot ）
2：重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作
3：递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序
动图：
代码：
算法分析
- 最佳情况：T(n) = O(nlogn)
- 最差情况：T(n) = O(n^2)
- 平均情况：T(n) = O(nlogn)
堆排序
这里用到了完全二叉树的部分性质
实现步骤：
1：将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆，此堆为初始的无序区
2：将堆顶元素 R[1]与最后一个元素 R[n]交换，此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足 R[1,2…n-1]<=R[n]
3：由于交换后新的堆顶 R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆，然后再次将 R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为 n-1，则整个排序过程完成
动图：
代码：
算法分析
- 最佳情况：T(n) = O(nlogn)
- 最差情况：T(n) = O(nlogn)
- 平均情况：T(n) = O(nlogn)
计数排序
实现步骤：
1：找出待排序的数组中最大和最小的元素；
2：统计数组中每个值为 i 的元素出现的次数，存入数组 C 的第 i 项
3：对所有的计数累加（从 C 中的第一个元素开始，每一项和前一项相加）
4：反向填充目标数组：将每个元素 i 放在新数组的第 C(i)项，每放一个元素就将 C(i)减去 1
动图：
代码：
算法分析
- 最佳情况：T(n) = O(n+k)
- 最差情况：T(n) = O(n+k)
- 平均情况：T(n) = O(n+k)
桶排序
实现步骤：
1：人为设置一个 BucketSize，作为每个桶所能放置多少个不同数值（例如当 BucketSize==5 时，该桶可以存放｛1,2,3,4,5｝这几种数字，但是容量不限，即可以存放 100 个 3）；
2：遍历输入数据，并且把数据一个一个放到对应的桶里去；
3：对每个不是空的桶进行排序，可以使用其它排序方法，也可以递归使用桶排序；
4：从不是空的桶里把排好序的数据拼接起来。
如果递归使用桶排序为各个桶排序，则当桶数量为 1 时要手动减小 BucketSize 增加下一循环桶的数量，否则会导致内存溢出。
图解：
代码：
算法分析
- 最佳情况：T(n) = O(n+k)
- 最差情况：T(n) = O(n+k)
- 平均情况：T(n) = O(n^2)
基数排序
实现步骤：
1：取得数组中的最大数，并取得位数
2：arr 为原始数组，从最低位开始取每个位组成 radix 数组
3：对 radix 进行计数排序（利用计数排序适用于小范围数的特点）
基数排序有两种方法：
MSD：从高位开始进行排序
LSD：从低位开始进行排序
动图：
代码：
算法分析
- 最佳情况：T(n) = O(n * k)
- 最差情况：T(n) = O(n * k)
- 平均情况：T(n) = O(n * k)
基数排序 、计数排序、桶排序都利用了桶的概念，但对桶的使用方法还是有区别的：
基数排序： 根据键值的每位数字来分配桶
计数排序： 每个桶只存储单一键值
桶排序： 每个桶存储一定范围的数值
