深入理解归并排序(Merge Sort)
2021-03-31
归并排序利用分治法将数组对半分割,递归排序子数组,最后合并排序后的子数组。其时间复杂度在最好、最坏和平均情况下均为 $O(n \log n)$,但需要额外的 $O(n)$ 空间来合并子数组。
归并排序利用分治法将数组对半分割,递归排序子数组,最后合并排序后的子数组。其时间复杂度在最好、最坏和平均情况下均为 $O(n \log n)$,但需要额外的 $O(n)$ 空间来合并子数组。
本文详细介绍了快速排序(Quick Sort)算法的原理,包括基准值选择策略、原位划分过程,并深入分析了其在最好、最坏及平均情况下的时空复杂度($O(n \log n)$ 至 $O(n^2)$),最后提供了 Java 和 C 语言的代码实现示例。
本文详细介绍了插入排序(Insertion Sort)算法的原理、伪代码、时空复杂度分析,并提供了 Java 和 C 语言的实现代码。插入排序在小规模数据或部分有序数据上表现优异。
本文详细介绍了经典排序算法——冒泡排序(Bubble Sort)的基本原理、伪代码、时空复杂度分析,并提供了 Java 代码实现。冒泡排序通过相邻元素的比较与交换,使最大元素逐步“冒泡”至序列末尾,时间复杂度为 O(n^2)。
本文详细介绍了经典的选择排序算法(Selection Sort)。包括其工作原理(寻找最小元素并交换)、图解演示、伪代码、性能分析($O(n^2)$ 时间复杂度,不稳定),以及 Java 代码实现,重点探讨了其不稳定性及原因。