Menu

归并排序–思路,代码

2018年2月7日 - 算法,数据结构

一 算法描述

归并排序算法(Merge Sort)是一种采用分治法(Divide-And-Conquer)的排序算法。分治策略将原问题划分为n个规模较小而结构与原问题相似的子问题,递归地解决这些子问题,然后在合并其结果,就得到原问题的解。分治模式在每一层递归上都包含三个步骤:分解、解决、合并。

归并排序需要使用额外的数组空间。

具体到归并算法,三个步骤分别为:

分解:将n个元素分成各含n/2个元素的子序列。这里采用分治法。

解决:用归并排序法对两个子序列递归的排序。

合并:合并两个已排序的子序列以得到排序结果,使用辅助数组。

 

public class Code_05_MergeSort {

public static void mergeSort(int[] arr) {

if (arr == null || arr.length < 2) {

return;

}

mergeSort(arr, 0, arr.length – 1);

}

public static void mergeSort(int[] arr, int l, int r) {

if (l == r) {

return;

}

int mid = l + ((rl) >> 1);

mergeSort(arr, l, mid);

mergeSort(arr, mid + 1, r);

merge(arr, l, mid, r);

}

publicstaticvoid merge(int[] arr, int l, int m, int r) {

int[] help = new int[rl + 1];

int i = 0;

int p1 = l;

int p2 = m + 1;

while (p1 <= m && p2 <= r) {

help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];

}

while (p1 <= m) {

help[i++] = arr[p1++];

}

while (p2 <= r) {

help[i++] = arr[p2++];

}

for (i = 0; i < help.length; i++) {

arr[l + i] = help[i];

}

}

 

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注

%d 博主赞过: