文档开发者中心
我的

Java分而治之03-合并排序

合并排序(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;

    }

}

 


点赞
收藏
回复
分享
举报
浏览216 发布于2020-10-20 09:54未知归属地
全部评论
最多点赞
最新发布
最早发布
暂无评论
暂无评论
写回答
新增插入模板功能
一键使用模板,快速填写内容,轻松发帖~
知道了
  • 为了保障您的信息安全,请勿上传您的敏感个人信息(如您的密码等信息)和您的敏感资产信息(如关键源代码、签名私钥、调试安装包、业务日志等信息),且您需自行承担由此产生的信息泄露等安全风险。
  • 如您发布的内容为转载内容,请注明内容来源。

我要发帖子

了解社区公约,与您携手共创和谐专业的开发者社区。