归并排序可以说是分治法的一个很形象的实例
归并排序与快排不同的是，归并排序重点在整合，简单的说把相对分区有序而内部
元素乱序的两区通过归并整合成有序的序列。
归并思路（分治法）：
分解：将n个元素一刀从中间分成两个序列
递归：将子序列递归的进行分区划分
解决：合并两个子序列（归并排序的重点）
归并排序的合并（以空间换时间）：
申请额外的和原数组大小相同的辅助空间，将原数组元素copy到辅助空间中
定义两个指针：left right ，其中left指向辅助空间头（第一区的头），right指向辅助空间中间元素下一个（第二区的头）比较大小，每次将小的元素覆盖到原数组，并且该指针后移
（Java代码示例）
public class MergeSort {
private static int[] helper;//辅助数组
public static void main(String[] args) {
int[] a = {5,15,8,20,6};
printArray(a);
sort(a);
printArray(a);
}
static void sort(int[] a) {
helper = new int[a.length];
mergeSort(a, 0, a.length - 1);
}
/**
*
* @param arr 待排序数组
* @param p 低位
* @param r 高位
*/
static void mergeSort(int[] arr, int p, int r) {
if(p < r) {
int mid = p + ((r - p)>>1);
mergeSort(arr, p, mid);//左侧排序
mergeSort(arr, mid+1, r);//右侧排序
merge(arr, p, mid, r);
}
}
static void printArray(int[] arr){
for(int i : arr){
System.out.print(i + " ");
}
System.out.println();
}
/**
*
* @param arr 待合并数组
* @param p 低位
* @param mid 中间位置
* @param r 高位
*/
static void merge(int[] arr, int p, int mid, int r) {
//arr中的数据拷贝到helper中
System.arraycopy(arr, p, helper, p, r-p+1);
//辅助数组的两个指针
int left = p;
int right = mid + 1;
//原始数组的指针
int current = p;
while(left <= mid&&right <= r) {
if(helper[left] <= helper[right]) {
arr[current] = helper[left];
current++;
left++;
}else {
arr[current] = helper[right];
current++;
right++;
}
}
while(left <= mid) {//左边没有到头,右边不到头也可以
arr[current] = helper[left];
current++;
left++;
}
}
}
网友评论