排序算法总结（个人理解版）：
- 第Ⅰ类:插入排序(后边元素依次与前边元素比较排序);
- 第Ⅱ类:选择排序(后边元素编组，选最小与最前元素交换位置)、谢尔排序(选择排序的改进，分组的方法不同)
- 第Ⅲ类:冒泡排序(1/2比较，2/3比较，依次类推)、快速排序(分组后冒泡)
- 第Ⅳ类:堆积排序(二叉树结构排序，建立堆)
| 平均时间复杂度 | 最坏时间复杂度 | 最好时间复杂度 | 空间复杂度 | 比较次数 | 交换次数 | 排序趟数 | |
|---|---|---|---|---|---|---|---|
| 插入排序 | O(n2) | O(n2) | O(n) | O(1) | 最好为n-1，最差为n(n-1)/2 | 最好为0，最差为n(n-1)/2 | n-1 |
| 谢尔排序 | O(nlog2n) | O(nlog2n) | O(n1.3) | O(1) | 最好为nlog2n，最差为n2 | 与gap有关，n-gap | log2n |
| 泡排序 | O(n2) | O(n2) | O(n) | O(1) | n(n-1)/2 | 逆序数 | 与原始状态有关 |
| 快速排序 | O(nlog2n) | O(n2) | O(nlog2n) | O(log2n)~O(n) | nlog2n，最差为n(n-1)/2 | 具体分析 | 与原始状态有关 |
| 选择排序 | O(n2) | O(n2) | O(n2) | O(1) | n(n-1)/2 | 0~(n-1) | n-1 |
| 堆积排序 | O(nlog2n) | O(nlog2n) | O(nlog2n) | O(1) | nlog2n | 具体分析 | n-1 |
