数据结构与算法 --- 排序算法（二）
💡
原文中文，约2800字，阅读约需7分钟。
📝
内容提要
归并排序和快速排序是时间复杂度为O(nlogn)的排序算法，它们使用分治思想将问题分解成子问题并递归解决。归并排序将数组分成两个子序列，递归排序后再合并成有序序列。归并排序的时间复杂度为O(nlogn)，空间复杂度为O(n)。
🎯
关键要点
- 归并排序和快速排序是时间复杂度为O(nlogn)的排序算法。
- 归并排序基于分治思想，将数组分成两个子序列进行递归排序，最后合并成有序序列。
- 分治算法的三个步骤是：分解、解决和合并。
- 归并排序的时间复杂度为O(nlogn)，空间复杂度为O(n)。
- 归并排序是稳定排序算法，合并过程保证相同元素的先后顺序不变。
- 归并排序的内存消耗主要来自于额外的临时数组和递归调用栈。
- 归并排序的递归深度为log(n)，每层递归需要保存一些临时变量。
➡️
