分治算法之快排和归并
2021-05-01 10:29
标签：oid 合并 code 代码分析 结果 分治算法 归并 ret int 归并排序模板： 观察上面代码分析可得： 分治算法之快排和归并 标签：oid 合并 code 代码分析 结果 分治算法 归并 ret int 原文地址：https://blog.51cto.com/thinklili/2507821
快速排序模板：
public void qucikSort(int[] array, int left, int right) {
if (left >= right) return;
int pivot = partition(array, left, right); //分，分的过程中已经治了
qucikSort(array, left, pivot - 1);
qucikSort(array, pivot+1, right);
}public void mergeSort(int[] array, int left, int right) {
if (left >= right) return;
int middle = (left + right) / 2;
mergeSort(array, left, middle);//分
mergeSort(array, middle + 1, right);//分
merge(array, left, middle, right);//治和合
}
快速排序是先将数组分为以pivot为元素左面小于pivot，右面大于等于pivot的两个序列，而递归的是qucikSort。说明在快排分治策略是以“分”为侧重点，没有明显的“合”过程。而归并排序先递归将数组分为左右子序列，在最后进行结果的“合”，归并排序的分支策略是以“治”，“合”为侧重点，而“分”很简单。
上一篇：Python语言基础概论
下一篇：希尔排序