二、排序
时间复杂度分析
排序算法 平均时间复杂度 最好 最坏 空间复杂度 稳定性 冒泡 O(n²) O(n) O(n²) O(1) 稳定 选择 O(n²) O(n²) O(n²) O(1) 不稳定 插入 O(n²) O(n) O(n²) O(1) 稳定 希尔 O(n^1.3) O(n) O(n²) O(1) 不稳定 堆 O(nlogn) O(nlogn) O(nlogn) O(1) 不稳定 快排 O(nlogn) O(nlogn) O(n²) O(logn) 不稳定 归并 O(nlogn) O(nlogn) O(nlogn) O(n) 稳定 计数 O(n+k) O(n+k) O(n+k) O(k) 稳定 基数 O(n x k) O(n x k) O(n x k) O(n+k) 稳定 桶 O(n+k) O(n+k) O(n²) O(n+k) 稳定
稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面。
不稳定：如果a原本在b的前面，而a=b，排序之后 a 可能会出现在 b 的后面。
时间复杂度：对排序数据的总的操作次数。反映当n变化时，操作次数呈现什么规律。
空间复杂度：是指算法在计算机内执行时所需存储空间的度量，它也是数据规模n的函数。
冒泡排序
- 思路：
- 比较相邻的元素。如果第一个比第二个大，就交换它们两个；
- 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
- 针对所有的元素重复以上的步骤，除了最后一个；
- 重复步骤1~3，直到排序完成。
- 代码：