排序算法面试专用

排序

• 稳定性：元素在排序后是否保持原来的相对顺序。

1.冒泡排序：

• n - 1次循环，每次循环比较前1-n-i个相邻的元素，把大的放后面

• 平均复杂度：$O(n^2)$

• 最好的情况

  • $O(n)$
  • 顺序

• 最坏的情况：

  • $O(n^2)$
  • 逆序

• 稳定

2.选择排序

• 循环n-1次把当前没有排好的序列中找到最小的那个元素放到前面
• 时间复杂度：
  • 最好，最坏，平均：$O(n^2)$
• 不稳定

3.插入排序

• 打扑克牌：每次拿到一个元素，插到合适的位置

• 时间复杂度：

  • 最好：$O(n)$,逆序
  • 最坏：$O(n^2)$，顺序

• 稳定

4.堆排序

• 建立二叉查找树
• 时间复杂度：
  • 最好最坏都是$O(nlogn)$
• 不稳定

5.归并排序

• 思路：

  • 取当前数组中间那个数，然后排好left、right，递归排下去

  • 排好 left 和right 后双指针，归并

• 时间复杂度：最好最坏都是$O(nlogn)$

• 稳定

6.快速排序

• 思想：
  • 基于分治：确定分界点$q[l],q[r],q[l+r>>1]$，这里面其中一个，把比分界点小的放到左边，比分界点大的放到右边，递归处理
• 时间复杂度：
  • 最好和平均都是$O(nlogn)$
  • 最坏：$O(n^2)$: 正序或逆序排列,递归n-1次
• 稳定性：不稳定

7.计数排序

• 思想：
  • 统计每一个数字出现的次数，然后按顺序输出
• 时间复杂度：最好最坏平均都是$O(n+m)$
• 稳定

8.桶排序

• 把数组里面的数按照大小均匀分布放在桶里面，然后桶里面自己排序，然后按顺序输出桶

• 时间复杂度

  • 最好和平均都是$O(n+k)$
  • 最坏的情况是元素大小很接近，一个桶里面会有很多元素:O(n^2)

• 稳定

9.希尔排序

• 按照间隔排序，间隔为n/2,每次排完后间隔除以2，最后间隔为1，就插入排序
• 平均：O(nlogn)，最好最坏带两个log
• 不稳定

10.基数排序

• 将整数按位分类，先按照个位，放到桶里面，每次按照顺序从桶里面取出来，再十位、百位、
• 时间复杂度:最好最坏平均$O(n\ast k)$
• 稳定