我们常见的排序分为以下几类：

1. 插入排序（直接插入排序，希尔排序）
2. 交换排序（冒泡排序，快速排序）
3. 选择排序（直接选择排序，堆排序）
4. 归并排序
5. 分配排序（箱排序，基数排序）

　　对于以上的排序有什么不同呢？

　　需要的辅助空间组多的：归并排序， 需要的辅助空间最小的：堆排序，平均速度最快的：快速排序

时间复杂度：

1. O(nlogn): 快速排序, 堆排序, 归并排序
2. O(n2): 直接插入排序， 冒泡排序， 直接选择排序
3. O(n): 基数排序

空间复杂度：

1. O(1): 直接插入排序, 冒泡排序, 直接选择排序
2. O(logn): 快速排序
3. O(n): 归并排序

Java算法