深入理解归并排序(Merge Sort)
2021-03-31
归并排序利用分治法将数组对半分割,递归排序子数组,最后合并排序后的子数组。其时间复杂度在最好、最坏和平均情况下均为 $O(n \log n)$,但需要额外的 $O(n)$ 空间来合并子数组。
归并排序利用分治法将数组对半分割,递归排序子数组,最后合并排序后的子数组。其时间复杂度在最好、最坏和平均情况下均为 $O(n \log n)$,但需要额外的 $O(n)$ 空间来合并子数组。
本文详细介绍了经典排序算法——冒泡排序(Bubble Sort)的基本原理、伪代码、时空复杂度分析,并提供了 Java 代码实现。冒泡排序通过相邻元素的比较与交换,使最大元素逐步“冒泡”至序列末尾,时间复杂度为 O(n^2)。