1.归并排序
具体参考前面的章节： (3)分治策略
归并排序是性能比较好的一种排序方法，它的时间复杂度是O(nlgn)，是典型的运用了分治思想的算法。归并排序的步骤如下：
- 分解：将待排序的n个元素分解成n/2的子序列。
- 解决：使用归并排序递归的排列两个子序列。
- 合并：将两个已排序的子序列合并得出结果。
代码如下：
/**
* @Project:
* @description: 归并排序
* @author: sunkang
* @create: 2018-08-15 20:19
* @ModificationHistory who when What
**/
public class MergerSort {
/**
* 归并排序算法
*分治方法核心思想为：
*1.分解： 分解两个子数组
*2.解决： 递归的解决两个子问题
*3.合并： 合并两个有序的子问题的集合
* @param A 将要排序的数组
* @param low 数组的要排序的地位
* @param high 数组排序的高位
*/
public void mergerSort(int[] A,int low ,int high ){
if(low < high){
//1.分解 分解两个子数组
int mid = (low+high)/2;
//2.解决 递归的解决两个子问题
mergerSort(A,low,mid);
mergerSort(A,mid+1,high);
//3合并 合并两个有序的子问题的集合
merger(A,low,mid ,high);
}
}
/**
* 进行子数组合并操作
* @param A 数组A
* @param low 低位
* @param mid 中位
* @param high 高位
*/
public void merger(int[] A ,int low ,int mid ,int high){
//得到子问题1的集合大小和子问题2的集合大小为n1 和n2
int n1 = mid - low + 1;
int n2 = high - mid;
//创建两个临时数组,然后赋值
int[] L = new int[n1];
int[] R = new int[n2];
for(int i =0;i < n1 ;i++){
L[i] = A[low + i];
}
for(int i = 0; i<n2; i++){
R[i] = A[mid + 1 + i];
}
//进行两个子数组合并
int i =0;
int j =0;
for(int k = low;k<= high;k++ ){
if(i == n1){
A[k] = R[j++];
}else if( j == n2){
A[k] = L[i++];
}else if( L[i] <= R[j]){
A[k] = L[i++];
}else{
A[k] = R[j++];
}
}
}
public void display(int[] arr){
for(int i :arr){
System.out.print(i+",");
}
System.out.println();
}
public static void main(String[] args) {
MergerSort sort = new MergerSort() ;
int[] arr = new int[]{1,2,7,4,3,9};
sort.mergerSort(arr,0,arr.length-1);
sort.display(arr);
}
}
下面分析一下归并排序的时间复杂度。
分解：分布步骤仅仅计算子数组的中间位置，需要常量时间，因此，D(n) = Θ(1);
解决： 递归的求解两个子规模为n/2的子问题，将贡献2T(n/2)的运行时间
合并： 注意一个具有n个 元素的子数组上merge需要 Θ(n)的时间，所以C(n)= Θ(n);
归并排序最坏情况运行时间T(n)的递归式如下：
归并排序递归式.png
