本文共 3558 字，大约阅读时间需要 11 分钟。

1 归并排序

1.1 原理

1.2 实现

import java.util.Arrays;/** * 归并排序 * * @author wgm * @since 2021/4/18 */public class MergeSort {       public static void main(String[] args) {           int[] ints = {   99, 100, -30, 0, 99, 2, -2, -15, 2, 2, 333, 666, 999, 27, 22, 13, 8, 7, 2, -30};        System.out.println("排序前：" + Arrays.toString(ints));        System.out.println("排序后：" + Arrays.toString(mergeSort(ints)));    }    private static int[] mergeSort(int[] ints) {           if (ints == null || ints.length <=1 ) {               return ints;        }        return mergeSort(ints, 0, ints.length, new int[ints.length]);    }    private static int[] mergeSort(int[] ints, int from, int to, int[] temp) {           if (from >= to - 1) {    // 留一个空间给mid            return ints;        }        int mid = (from + to) / 2;        mergeSort(ints, from, mid, temp);        mergeSort(ints, mid, to, temp);        merge(ints, from, mid, to, temp);        return ints;    }    private static void merge(int[] ints, int from, int mid, int to, int[] temp) {           int p = from;        int q = mid;        int i = from;        while (p < mid && q < to) {               if (ints[p] <= ints[q]) {                   temp[i] = ints[p];                p++;            } else {                   temp[i] = ints[q];                q++;            }            i++;        }        while (p < mid) {               temp[i] = ints[p];            p++;            i++;        }        while (q < to) {               temp[i] = ints[q];            q++;            i++;        }        i = from;        while (i < to) {               ints[i] = temp[i];            i++;        }    }}

1.3 测试

D:\program\Java\jdk1.8.0_241\bin\java.exe -agentlib:jdwp=transport=dt_socket,address=127.0.0.1:49367,suspend=y,server=n "-javaagent:C:\Users\GMWANG~1\AppData\Local\Temp\captureAgent1011jars\debugger-agent.jar" -Dfile.encoding=UTF-8 -classpath "D:\program\Java\jdk1.8.0_241\jre\lib\charsets.jar;D:\program\Java\jdk1.8.0_241\jre\lib\deploy.jar;D:\program\Java\jdk1.8.0_241\jre\lib\ext\access-bridge-64.jar;D:\program\Java\jdk1.8.0_241\jre\lib\ext\cldrdata.jar;D:\program\Java\jdk1.8.0_241\jre\lib\ext\dnsns.jar;D:\program\Java\jdk1.8.0_241\jre\lib\ext\jaccess.jar;D:\program\Java\jdk1.8.0_241\jre\lib\ext\jfxrt.jar;D:\program\Java\jdk1.8.0_241\jre\lib\ext\localedata.jar;D:\program\Java\jdk1.8.0_241\jre\lib\ext\nashorn.jar;D:\program\Java\jdk1.8.0_241\jre\lib\ext\sunec.jar;D:\program\Java\jdk1.8.0_241\jre\lib\ext\sunjce_provider.jar;D:\program\Java\jdk1.8.0_241\jre\lib\ext\sunmscapi.jar;D:\program\Java\jdk1.8.0_241\jre\lib\ext\sunpkcs11.jar;D:\program\Java\jdk1.8.0_241\jre\lib\ext\zipfs.jar;D:\program\Java\jdk1.8.0_241\jre\lib\javaws.jar;D:\program\Java\jdk1.8.0_241\jre\lib\jce.jar;D:\program\Java\jdk1.8.0_241\jre\lib\jfr.jar;D:\program\Java\jdk1.8.0_241\jre\lib\jfxswt.jar;D:\program\Java\jdk1.8.0_241\jre\lib\jsse.jar;D:\program\Java\jdk1.8.0_241\jre\lib\management-agent.jar;D:\program\Java\jdk1.8.0_241\jre\lib\plugin.jar;D:\program\Java\jdk1.8.0_241\jre\lib\resources.jar;D:\program\Java\jdk1.8.0_241\jre\lib\rt.jar;D:\project\untitled\out\production\untitled;D:\program\JetBrains\IntelliJ IDEA 2020.1\lib\idea_rt.jar" MergeSortConnected to the target VM, address: '127.0.0.1:49367', transport: 'socket'排序前：[99, 100, -30, 0, 99, 2, -2, -15, 2, 2, 333, 666, 999, 27, 22, 13, 8, 7, 2, -30]排序后：[-30, -30, -15, -2, 0, 2, 2, 2, 2, 7, 8, 13, 22, 27, 99, 99, 100, 333, 666, 999]Disconnected from the target VM, address: '127.0.0.1:49367', transport: 'socket'Process finished with exit code 0