合并排序(Merge Sort)算法是将两个(或两个以上)有序表合并成一个新的有序表,即把待排序序列分为若干个子序列,每个子序列是有序的。然后再把有序子序列合并为整体有序序列。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。因此,合并排序也叫归并排序。
合并排序算法是采用分治法的一个非常典型的应用。时间复杂度O(nlogn),空间复杂度O(nlogn)。
算法思路
合并排序算法思路如下:
l 第一步,将要排序的列表一分为二,直到分成每个列表只有一个数字为止。
l 第二步,将两个有序的列表进行比较排序,合成一个列表,直到其中一个列表历遍完了,再将另一个剩下的列表合并进去。
举例说,比如我们有这样的一个序列: [88, 3, 5, 7, 5,9, 4, 6, 8, 99]。如果要进行合并排序,则采用如下的步骤
一分为二:A:[88, 3, 5, 7, 5]; B[9, 4, 6, 8, 99]
一分为二:AA:[88,3];AB[5,7,5];BA[9,4];BB[6,8,99];
一分为二:AAA[88];AAB[3];ABA[5];ABB[7,5];
BAA[9];BAB[4];BBA[6];BBB[8,99]
一分为二:AAA[88];AAB[3];ABA[5];ABBA[7];ABBB[5];
BAA[9];BAB[4];BBA[6];BBBA[8];BBBB[99];
合并排序:
AAA + AAB = [3,88]
ABBA + ABBB = [5,7]
ABA + [5,7] = [5,5,7]
a = [3,88] + [5,5,7] = [3,5,5,7,88]
---------------------------------------
BAA + BAB =[4,9]
BBBA + BBBB = [8,99]
BBA + [8,99] = [6,8,99]
b = [4,9] + [6,8,99] = [4,6,8,9,99]
-----------------------------------------
并归a和b:
a=[3,5,5,7,88]
b=[4,6,8,9,99]
c = [3,4,5,5,6,7,8,9,88,99]
算法实现
合并排序算法思路如下:
package com.waylau.java.demo.algorithm;
/**
* Merge sort.
* <p>
* Family: Merging.<br>
* Space: In-place.<br>
* Stable: True.<br>
* <p>
* Average case = O(n*log n)<br>
* Worst case = O(n*log n)<br>
* Best case = O(n*log n)<br>
* <p>
* @author <a href="https://waylau.com">Way Lau</a>
* @since 2020-10-20
*/
@SuppressWarnings("unchecked")
public class MergeSort<T extends Comparable<T>> {
public static enum SPACE_TYPE { IN_PLACE, NOT_IN_PLACE }
private MergeSort() { }
public static <T extends Comparable<T>> T[] sort(SPACE_TYPE type, T[] unsorted) {
sort(type, 0, unsorted.length, unsorted);
return unsorted;
}
private static <T extends Comparable<T>> void sort(SPACE_TYPE type, int start, int length, T[] unsorted) {
if (length > 2) {
int aLength = (int) Math.floor(length / 2);
int bLength = length - aLength;
sort(type, start, aLength, unsorted);
sort(type, start + aLength, bLength, unsorted);
if (type == SPACE_TYPE.IN_PLACE) {
mergeInPlace(start, aLength, start + aLength, bLength, unsorted);
} else {
mergeWithExtraStorage(start, aLength, start + aLength, bLength, unsorted);
}
} else if (length == 2) {
T e = unsorted[start + 1];
if (e.compareTo(unsorted[start]) < 0) {
unsorted[start + 1] = unsorted[start];
unsorted[start] = e;
}
}
}
private static <T extends Comparable<T>> void mergeInPlace(int aStart, int aLength, int bStart, int bLength, T[] unsorted) {
int i = aStart;
int j = bStart;
int aSize = aStart + aLength;
int bSize = bStart + bLength;
while (i < aSize && j < bSize) {
T a = unsorted[i];
T b = unsorted[j];
if (b.compareTo(a) < 0) {
// 把所有东西都移到正确的位置
System.arraycopy(unsorted, i, unsorted, i+1, j-i);
unsorted[i] = b;
i++;
j++;
aSize++;
} else {
i++;
}
}
}
private static <T extends Comparable<T>> void mergeWithExtraStorage(int aStart, int aLength, int bStart, int bLength, T[] unsorted) {
int count = 0;
T[] output = (T[]) new Comparable[aLength + bLength];
int i = aStart;
int j = bStart;
int aSize = aStart + aLength;
int bSize = bStart + bLength;
while (i < aSize || j < bSize) {
T a = null;
if (i < aSize) {
a = unsorted[i];
}
T b = null;
if (j < bSize) {
b = unsorted[j];
}
if (a != null && b == null) {
output[count++] = a;
i++;
} else if (b != null && a == null) {
output[count++] = b;
j++;
} else if (b != null && b.compareTo(a) <= 0) {
output[count++] = b;
j++;
} else {
output[count++] = a;
i++;
}
}
int x = 0;
int size = aStart + aLength + bLength;
for (int y = aStart; y < size; y++) {
unsorted[y] = output[x++];
}
}
}
单元测试如下:
package com.waylau.java.demo.algorithm;
import static org.junit.jupiter.api.Assertions.assertTrue;
import java.util.Random;
import org.junit.jupiter.api.MethodOrderer;
import org.junit.jupiter.api.Order;
import org.junit.jupiter.api.Test;
import org.junit.jupiter.api.TestMethodOrder;
/**
* MergeSort Test.
*
* @author <a href="https://waylau.com">Way Lau</a>
* @since 2020-10-20
*/
@TestMethodOrder(MethodOrderer.OrderAnnotation.class)
public class MergeSortTests {
private static final Random RANDOM = new Random();
private static final int SIZE = 10000;
private static Integer[] unsorted = null; // 未排序
private static Integer[] sorted = null; // 已排序
private static Integer[] reverse = null; // 反转
static {
unsorted = new Integer[SIZE];
int i = 0;
while (i < unsorted.length) {
int j = RANDOM.nextInt(unsorted.length * 10);
unsorted[i++] = j;
}
sorted = new Integer[SIZE];
for (i = 0; i < sorted.length; i++) {
sorted[i] = i;
}
reverse = new Integer[SIZE];
for (i = (reverse.length - 1); i >= 0; i--) {
reverse[i] = (SIZE - 1) - i;
}
}
@Order(1)
@Test
public void testMergeSortsInPlace() {
// Merge sort
Integer[] result = MergeSort.sort(MergeSort.SPACE_TYPE.IN_PLACE, unsorted.clone());
assertTrue(check(result));
result = MergeSort.sort(MergeSort.SPACE_TYPE.IN_PLACE, sorted.clone());
assertTrue(check(result));
result = MergeSort.sort(MergeSort.SPACE_TYPE.IN_PLACE, reverse.clone());
assertTrue(check(result));
}
@Order(2)
@Test
public void testMergeSortsNotInPlace() {
// Merge sort
Integer[] result = MergeSort.sort(MergeSort.SPACE_TYPE.NOT_IN_PLACE, unsorted.clone());
assertTrue( check(result));
result = MergeSort.sort(MergeSort.SPACE_TYPE.NOT_IN_PLACE, sorted.clone());
assertTrue(check(result));
result = MergeSort.sort(MergeSort.SPACE_TYPE.NOT_IN_PLACE, reverse.clone());
assertTrue(check(result));
}
private static final boolean check(Integer[] array) {
for (int i = 1; i<array.length; i++) {
if (array[i-1]>array[i])
return false;
}
return true;
}
}





































苏公安网备 32011402010933号