数据结构入门精讲 第8篇 全面讲解所有排序算法 (2)

上一篇文章中讲述了一些关于冒泡排序和快速排序等其他算法。
接下来我们将继续探讨有关排序算法的知识。

目录

• • 归并排序
  • 堆排序
  • 选择排序
  • 计数排序
  • 基数排序
  • 排序总结

归并排序

基于归并操作实现的一种高效且稳定的排序方法是一种经典的分治法（Divide and Conquer）应用实例。该排序方法通过将一组无序数据划分为多个小数据块进行处理后，在完成各小块内部排序的基础上逐步实现整体数据集的有效排列；具体而言，则是先确保每个小数据块内部元素完全有序，并逐步实现区域间的有序状态；若两个相邻的排好序的小数据块需要整合成一个更大的排好序的大数据块，则称这一过程为双线合并（Two-way merge）。

• 归并排序算法的时间复杂度通常被认为是O(n \log n)，然而，在实现过程中需要预留额外的空间以用于存储中间数组。通过分析可知，空间复杂度计算结果表明所需额外空间与数据规模呈线性关系。

代码

    #include <stdio.h>