排序算法面试专用

码农世界 2024-05-19 后端 63 次浏览 0个评论

排序

稳定性：元素在排序后是否保持原来的相对顺序。
1.冒泡排序：
- n - 1次循环，每次循环比较前1-n-i个相邻的元素，把大的放后面
- 平均复杂度： O ( n 2 ) O(n^2) O(n2)
- 最好的情况
  - O ( n ) O(n) O(n)
  - 顺序
  - 最坏的情况：
    - O ( n 2 ) O(n^2) O(n2)
    - 逆序
    - 稳定
      
      2.选择排序
      - 循环n-1次把当前没有排好的序列中找到最小的那个元素放到前面
      - 时间复杂度：
        最好，最坏，平均： O ( n 2 ) O(n^2) O(n2)
        不稳定
        3.插入排序
        
        打扑克牌：每次拿到一个元素，插到合适的位置
        
        时间复杂度：
        
        最好： O ( n ) O(n) O(n),逆序
        最坏： O ( n 2 ) O(n^2) O(n2)，顺序
        
        稳定
        
        4.堆排序
        
        建立二叉查找树
        时间复杂度：
        最好最坏都是 O ( n l o g n ) O(nlogn) O(nlogn)
        不稳定
        5.归并排序
        
        思路：
        
        取当前数组中间那个数，然后排好left、right，递归排下去
        
        排好 left 和right 后双指针，归并
        
        时间复杂度：最好最坏都是 O ( n l o g n ) O(nlogn) O(nlogn)
        
        稳定
        
        6.快速排序
        
        思想：
        基于分治：确定分界点 q [ l ] , q [ r ] , q [ l + r > > 1 ] q[l], q[r], q[l + r >> 1] q[l],q[r],q[l+r>>1]，这里面其中一个，把比分界点小的放到左边，比分界点大的放到右边，递归处理
        时间复杂度：
        最好和平均都是 O ( n l o g n ) O(nlogn) O(nlogn)
        最坏： O ( n 2 ) O(n^2) O(n2): 正序或逆序排列,递归n-1次
        稳定性：不稳定
        7.计数排序
        
        思想：
        统计每一个数字出现的次数，然后按顺序输出
        时间复杂度：最好最坏平均都是 O ( n + m ) O(n+m) O(n+m)
        稳定
        8.桶排序
        
        把数组里面的数按照大小均匀分布放在桶里面，然后桶里面自己排序，然后按顺序输出桶
        
        时间复杂度
        
        最好和平均都是 O ( n + k ) O(n + k) O(n+k)
        最坏的情况是元素大小很接近，一个桶里面会有很多元素:O(n^2)
        
        稳定
        
        9.希尔排序
        
        按照间隔排序，间隔为n/2,每次排完后间隔除以2，最后间隔为1，就插入排序
        平均：O(nlogn)，最好最坏带两个log
        不稳定
        10.基数排序
        
        将整数按位分类，先按照个位，放到桶里面，每次按照顺序从桶里面取出来，再十位、百位、
        时间复杂度:最好最坏平均 O ( n ∗ k ) O(n*k) O(n∗k)
        稳定