不同排序算法比较

排序方法	平均时间	最好时间	最差时间	空间复杂度	稳定性
O(n^2) 算法
冒泡排序	O(n^2)	O(n)	O(n^2)	O(1)	稳定
插入排序	O(n^2)	O(n)	O(n^2)	O(1)	稳定
选择排序	O(n^2)	O(n^2)	O(n^2)	O(1)	不稳定
O(nlogn) 算法
归并排序	O(nlogn)	O(nlogn)	O(nlogn)	O(n)	稳定
快速排序	O(nlogn)	O(nlogn)	O(n^2)	O(1)	不稳定
堆排序	O(nlogn)	O(nlogn)	O(nlogn)	O(1)	不稳定
O(n) 算法
桶排序	O(n)				稳定
计数排序	O(n+k)				稳定
基数排序	O(dn)				稳定

几个问题

1. 插入排序和冒泡排序如何选择？
对于冒泡排序，元素交换次数固定，等于初始逆序度；而对于插入排序，元素移动次数固定，等于初始逆序度。但是完成一次交换需要 3 个基本操作，而移动只需要 1 个，因此插入排序性能更好

2. 归并排序为什么没有快速排序运用广泛？
尽管快速排序最差时间复杂度为 O(n^2) ，而归并排序能稳定保持 O(nlogn) ，但是因为归并排序不是原地排序，需要占用更多的内存。且可以通过一定的技巧构造 partition() 函数，使得快排的复杂度尽可能接近 O(nlogn)

3. 快速排序为什么比堆排序更常用？

• 堆排序对缓存不友好：快速排序是局部顺序访问数组，而堆排序是不连续的
• 堆排序操作次数更多：尽管时间复杂度相同，快排的交换次数不会超过元素的逆序度，堆排序的建堆操作会带来更多的交换次数。极端情况：一个有序数组经过建堆操作会变成无序数组

4. 桶排序，计数排序，基数排序分别适用的场景？

• 桶排序：10 GB 订单数据，几百 MB 内存，对订单按金额进行排序
• 计数排序：按照年龄，对 100 万用户进行排序
• 基数排序：对 10 万个手机号码，按照从小到大进行排序

衡量排序算法效率的指标

• 算法的稳定性：大小相同的元素，排序后，前后顺序是否改变

• 算法的内存消耗：排序算法的空间复杂度

• 算法的执行效率：排序算法的时间复杂度

  • 最好、最坏、平均时间复杂度：了解排序算法在各种情况下（有序，无序）的性能
  • 时间复杂度的系数、常数、低阶：对于小规模数据，尤其重要
  • 比较次数或交换、移动次数