归并排序的原理及java代码实现

归并排序的原理及java代码实现

概述

归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。

归并排序采用的是递归来实现，属于“分而治之”，将目标数组从中间一分为二，之后分别对这两个数组进行排序，排序完毕之后再将排好序的两个数组“归并”到一起，归并排序最重要的也就是这个“归并”的过程，归并的过程中需要额外的跟需要归并的两个数组长度一致的空间。

效果图：

步骤

申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列

设定两个指针，最初位置分别为两个已经排序序列的起始位置

比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置

重复步骤3直到某一指针达到序列尾

将另一序列剩下的所有元素直接复制到合并序列尾

实例

原始数据：

3 5 2 6 2

归并的前提是将数组分开，一分为二，再一分为二，分到不能再分，进行归并。

第一轮分隔，索引2 ((0+4)/2=2) 为中间

[3 5 2] [6 2]

第二轮分隔，对[3 5 2]进行分隔

[3 5] [2] [6 2]

第三轮分隔，对[3 5]进行分隔

[3] [5] [2] [6 2]

合并[3] [5]

[3 5] [2] [6 2]

合并[3 5] [2]

[2 3 5] [6 2]

第四轮分隔，对[6 2]进行分隔

[2 3 5] [6] [2]

合并[6] [2]

[2 3 5] [2 6]

合并[2 3 5] [2 6]

[2 2 3 5 6]

代码实现(java)

package com.coder4j.main.arithmetic.sorting;

public class Merge {

private static int mark = 0;

/**

* 归并排序

*

* @param array

* @param low

* @param high

* @return

*/

private static int[] sort(int[] array, int low, int high) {

int mid = (low + high) / 2;

if (low < high) {

mark++;

System.out.println("正在进行第" + mark + "次分隔，得到");

System.out.println("[" + low + "-" + mid + "] [" + (mid + 1) + "-" + high + "]");

// 左边数组

sort(array, low, mid);

// 右边数组

sort(array, mid + 1, high);

// 左右归并

merge(array, low, myYGdPid, high);

}

return array;

}

/**

* 对数组进行归并

*

* @param array

* @param low

* @param mid

* @param high

*/

private static void merge(int[] array, int low, int mid, int high) {

System.out.println("合并:[" + low + "-" + mid + "] 和 [" + (mid + 1) + "-" + high + "]");

int[] temp = new int[high - low + 1];

int i = low;// 左指针

int j = mid + 1;// 右指针

int k = 0;

// 把较小的数先移到新数组中

while (i <= mid && j <= high) {

if (array[i] < array[j]) {

temp[k++] = array[i++];

} else {

temp[k++] = array[j++];

}

}

// 两个数组之一可能存在剩余的元素

// 把左边剩余的数移入数组

while (i <= mid) {

temp[k++] = array[i++];

}

// 把右边边剩余的数移入数组

while (j <= high) {

temp[k++] = array[j++];

}

// 把新数组中的数覆盖array数组

for (int m = 0; m < temp.length; m++) {

array[m + low] = temp[m];

}

}

/**

* 归并排序

*

* @param arrayyYGdP

* @return

*/

public static int[] sort(int[] array) {

return sort(array, 0, array.length - 1);

}

public static void main(String[] args) {

int[] array = { 3, 5, 2, 6, 2 };

int[] sorted = sort(array);

System.out.println("最终结果");

for (int i : sorted) {

System.out.print(i + " ");

}

}

}

测试输出结果：

正在进行第1次分隔，得到

[0-2] [3-4]

正在进行第2次分隔，得到

[0-1] [2-2]

正在进行第3次分隔，得到

[0-0] [1-1]

合并:[0-0] 和 [1-1]

合并:[0-1] 和 [2-2]

正在进行第4次分隔，得到

[3-3] [4-4]

合并:[3-3] 和 [4-4]

合并:[0-2] 和 [3-4]

最终结果

2 2 3 5 6

经测试，与实例中结果一致。

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。