共计 839 个字符,预计需要花费 3 分钟才能阅读完成。
疾速排序理论就是二叉树的前序遍历,归并排序理论就是二叉树的后序遍历。
疾速排序的逻辑是,若要对 nums[lo..hi]
进行排序,咱们先找一个分界点 p
,通过替换元素使得 nums[lo..p-1]
都小于等于 nums[p]
,且 nums[p+1..hi]
都大于 nums[p]
,而后递归地去 nums[lo..p-1]
和 nums[p+1..hi]
中寻找新的分界点,最初整个数组就被排序了。
疾速排序的代码框架如下:
void sort(int[] nums, int lo, int hi) {
/****** 前序遍历地位 ******/
// 通过替换元素构建分界点 p
int p = partition(nums, lo, hi);
/************************/
sort(nums, lo, p - 1);
sort(nums, p + 1, hi);
}
先结构分界点,而后去左右子数组结构分界点,你看这不就是一个二叉树的前序遍历吗
再说说归并排序的逻辑,若要对 nums[lo..hi]
进行排序,咱们先对 nums[lo..mid]
排序,再对 nums[mid+1..hi]
排序,最初把这两个有序的子数组合并,整个数组就排好序了。
归并排序的代码框架如下:
void sort(int[] nums, int lo, int hi) {int mid = (lo + hi) / 2;
// 排序 nums[lo..mid]
sort(nums, lo, mid);
// 排序 nums[mid+1..hi]
sort(nums, mid + 1, hi);
/****** 后序地位 ******/
// 合并 nums[lo..mid] 和 nums[mid+1..hi]
merge(nums, lo, mid, hi);
/*********************/
}
先对左右子数组排序,而后合并(相似合并有序链表的逻辑),你看这是不是二叉树的后序遍历框架?另外,这不就是传说中的分治算法嘛,不过如此呀
说了这么多,旨在阐明,二叉树的算法思维的使用宽泛,甚至能够说,只有波及递归,都能够形象成二叉树的问题。
正文完