10、【排序】歸并排序

1、概述

  • 歸并排序（Merge Sort）是一種高級(jí)排序算法。

  • 歸并排序的時(shí)間復(fù)雜度是O(nlogn)，當(dāng)然，這個(gè)是存在優(yōu)化空間的。

  • 整個(gè)排序的過(guò)程大體上就可以分為“歸”、“并”兩個(gè)步驟?！皻w”指的是“遞歸”，“并”是“合并”。

  • 歸并排序不是“就地”排序，因?yàn)樵凇安ⅰ钡臅r(shí)候，需要開(kāi)辟空間來(lái)完成。

2、思想

  • 歸并排序的思想是：將需要排序的數(shù)據(jù)一分為二，分別對(duì)兩個(gè)部分進(jìn)行排序，排好序后，再將兩組有序的數(shù)據(jù)進(jìn)行合并。

  • 歸并排序中的一個(gè)重要的思想是“遞歸”，意思是，原始數(shù)據(jù)一分為二后，然后每一組數(shù)據(jù)再一分為二，直到每組中只有一個(gè)數(shù)據(jù)；之后每?jī)山M再按序合并，合并后的數(shù)據(jù)又形成一個(gè)新的組，再與另外一個(gè)組合二為一，直到合并完所有數(shù)據(jù)。

歸并排序思想

注意，雖然上圖中所繪制出來(lái)的是拆分，但是實(shí)際上的“歸并”依靠的是索引區(qū)間的變化，所有的數(shù)據(jù)仍然是一個(gè)完整的數(shù)組。

歸并排序-遞歸宏觀語(yǔ)義

3、動(dòng)畫(huà)演示

歸并排序-偶數(shù)-動(dòng)畫(huà)演示
歸并排序-奇數(shù)-動(dòng)畫(huà)演示

4、Java 代碼實(shí)現(xiàn)

4.1、合并的實(shí)現(xiàn)

  • 在編寫(xiě)歸并排序算法之前，需要先編寫(xiě)一個(gè)用于“合并”的方法，能夠?qū)山M有序數(shù)據(jù)合并（或稱(chēng)“調(diào)整”）成一組有序數(shù)據(jù)的方法。比較特殊的是，為了配合實(shí)現(xiàn)歸并排序，這里的兩組數(shù)據(jù)是在一起的即處在一個(gè)數(shù)組中，方法簽名是void merge(E[] arr, int l, int r, int mid)，含義是“將arr中索引區(qū)間為[l,mid]這一有序部分與索引區(qū)間為[mid+1,r]這一有序部分按序合并”（注意，雖然字面上理解起來(lái)merge這一詞更像是合并兩個(gè)數(shù)組，但實(shí)際上merge的對(duì)象是一個(gè)數(shù)組中的兩部分）。

  • merge方法：

import java.util.Arrays;

public class Main {

    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 7, 9, 13, 0, 2, 4, 6, 8};
        System.out.println(arrString(arr));

        merge(arr, 1, arr.length - 2, 5);
        System.out.println(arrString(arr));
    }

    /**
     * 將 arr 的 [l,mid] 區(qū)間的有序部分與 [mid+1,r] 區(qū)間的有序部分合并（或稱(chēng)“調(diào)整”）為 [l,r] 整個(gè)區(qū)間有序
     *
     * 為配合歸并排序，會(huì)直接對(duì) arr 進(jìn)行調(diào)整，所以調(diào)整之前需要拷貝一份原始對(duì)應(yīng)索引區(qū)間的數(shù)據(jù)
     */
    private static void merge(int[] arr, int l, int r, int mid) {
        int[] temp = Arrays.copyOfRange(arr, l, r + 1);
        int i = l;
        int j = mid + 1;
        for (int k = l; k <= r; k++) {
            if (i <= mid && j <= r) {
                if (temp[i - l] < temp[j - l]) {
                    arr[k] = temp[i - l];
                    i++;
                } else {
                    arr[k] = temp[j - l];
                    j++;
                }
            } else if (i > mid) {
                arr[k] = temp[j - l];
                j++;
            } else {
                arr[k] = temp[i - l];
                i++;
            }
        }
    }

    private static String arrString(int[] arr) {
        StringBuilder sb = new StringBuilder("[");
        for (int i = 0; i < arr.length; i++) {
            sb.append(arr[i]);
            if (i != arr.length - 1) {
                sb.append(", ");
            }
        }
        sb.append("]");
        return sb.toString();
    }

}

[1, 3, 5, 7, 9, 13, 0, 2, 4, 6, 8]
[1, 0, 2, 3, 4, 5, 6, 7, 9, 13, 8]

上面代碼在main方法調(diào)用merge方法，將數(shù)組{1, 3, 5, 7, 9, 13, 0, 2, 4, 6, 8}的索引區(qū)間為[1,5]的有序部分與索引區(qū)間為[6,9]的有序部分調(diào)整為整個(gè)[1,9]區(qū)間均為有序。

在merge方法中，為了配合后面的歸并算法的實(shí)現(xiàn)，直接在原始的數(shù)組上進(jìn)行調(diào)整，所以，需要先將整個(gè)索引區(qū)間中的數(shù)據(jù)拷貝出來(lái)（所以歸并排序不是“就地”排序），在拷貝出的數(shù)據(jù)中依次比較兩部分有序數(shù)據(jù)，根據(jù)比較的結(jié)果逐一放回原數(shù)組。由于拷貝出的數(shù)據(jù)索引是從0開(kāi)始，所以會(huì)出現(xiàn)下面圖所表示的偏移量的問(wèn)題。

歸并排序-合并-偏移量

如果不理解，可以采取的一個(gè)較容易理解的方案，就是在一開(kāi)始用新的變量來(lái)在拷貝出的數(shù)組中標(biāo)注兩個(gè)有序數(shù)據(jù)的起始。
在拷貝出的數(shù)據(jù)中：
0一定是第一個(gè)有序數(shù)據(jù)部分的起始，mid - l是第一個(gè)有序數(shù)據(jù)部分的邊界；
mid + 1 - l是第二個(gè)有序數(shù)據(jù)部分的起始，r - l是第二個(gè)有序數(shù)據(jù)部分的邊界。

    /**
     * 將 arr 的 [l,mid] 區(qū)間的有序部分與 [mid+1,r] 區(qū)間的有序部分合并（或稱(chēng)“調(diào)整”）為 [l,r] 整個(gè)區(qū)間有序
     *
     * 為配合歸并排序，會(huì)直接對(duì) arr 進(jìn)行調(diào)整，所以調(diào)整之前需要拷貝一份原始數(shù)據(jù)
     */
    private static void merge(int[] arr, int l, int r, int mid) {
        int[] temp = Arrays.copyOfRange(arr, l, r + 1);
        
        // 拷貝出的數(shù)組中，如下是關(guān)鍵的變量

        // partOneIndex: 用于遍歷第一部分有序數(shù)據(jù)
        int partOneIndex = 0;
        // partTwoIndex: 第一部分有序數(shù)據(jù)的邊界索引
        int partOneBound = mid - l;

        // partOneIndex: 用于遍歷第二部分有序數(shù)據(jù)
        int partTwoIndex = mid + 1 - l;
        // partTwoIndex: 第二部分有序數(shù)據(jù)的邊界索引
        int partTwoBound = r - l;

        for (int cur = l; cur <= r; cur++) {
            if (partOneIndex <= partOneBound && partTwoIndex <= partTwoBound) {
                if (temp[partOneIndex] < temp[partTwoIndex]) {
                    arr[cur] = temp[partOneIndex];
                    partOneIndex++;
                } else {
                    arr[cur] = temp[partTwoIndex];
                    partTwoIndex++;
                }
            } else if (partOneIndex > partOneBound) {
                arr[cur] = temp[partTwoIndex];
                partTwoIndex++;
            } else {
                arr[cur] =  temp[partOneIndex];
                partOneIndex++;
            }
        }
    }

4.2、歸并排序?qū)崿F(xiàn)

  • 對(duì)整數(shù)數(shù)組排序
import java.util.Arrays;

public class MergeSortInteger {

    public static void mergeSort(int[] arr, boolean isAscending) {
        mergeSort(arr, 0, arr.length - 1, isAscending);
    }
    
    // 遞歸
    // 對(duì) arr 數(shù)組的 [l,r] 區(qū)間進(jìn)行排序 
    private static void mergeSort(int[] arr, int l, int r, boolean isAscending) {
        if (l >= r) {
            return;
        }
        // int mid = l + (r - l) / 2;
        int mid = (l + r) / 2;
        mergeSort(arr, l, mid, isAscending);
        mergeSort(arr, mid + 1, r, isAscending);
        // 排序后合并
        merge(arr, l, mid, r, isAscending);
    }

    private static void merge(int[] arr, int l, int mid, int r, boolean isAscending) {
        int[] temp = Arrays.copyOfRange(arr, l, r + 1);
        int partOneIndex = 0;
        int partOneBound = mid - l;
        int partTwoIndex = mid + 1 - l;
        int partTwoBound = r - l;

        for (int cur = l; cur <= r; cur++) {
            if (partOneIndex <= partOneBound && partTwoIndex <= partTwoBound) {
                if (temp[partOneIndex] < temp[partTwoIndex]) {
                    if (isAscending) {
                        arr[cur] = temp[partOneIndex];
                        partOneIndex++;
                    } else {
                        arr[cur] = temp[partTwoIndex];
                        partTwoIndex++;
                    }
                } else {
                    if (isAscending) {
                        arr[cur] = temp[partTwoIndex];
                        partTwoIndex++;
                    } else {
                        arr[cur] = temp[partOneIndex];
                        partOneIndex++;
                    }
                }
            } else if (partOneIndex > partOneBound) {
                arr[cur] = temp[partTwoIndex];
                partTwoIndex++;
            } else {
                arr[cur] = temp[partOneIndex];
                partOneIndex++;
            }
        }

    }

}
  • 使用 Java 的泛型機(jī)制，對(duì)排序的數(shù)據(jù)種類(lèi)進(jìn)行拓展
import java.util.Arrays;

public class MergeSort {

    public static <E extends Comparable<E>> void mergeSort(E[] arr, boolean isAscending) {
        mergeSort(arr, 0, arr.length - 1, isAscending);
    }

    private static <E extends Comparable<E>> void mergeSort(E[] arr, int l, int r, boolean isAscending) {
        if (l >= r) {
            return;
        }
        int mid = (l + r) / 2;
        mergeSort(arr, l, mid, isAscending);
        mergeSort(arr, mid + 1, r, isAscending);
        merge(arr, l, mid, r, isAscending);
    }

    private static <E extends Comparable<E>> void merge(E[] arr, int l, int mid, int r, boolean isAscending) {
        E[] temp = Arrays.copyOfRange(arr, l, r + 1);
        int partOneIndex = 0;
        int partOneBound = mid - l;
        int partTwoIndex = mid + 1 - l;
        int partTwoBound = r - l;

        for (int cur = l; cur <= r; cur++) {
            if (partOneIndex <= partOneBound && partTwoIndex <= partTwoBound) {
                if (temp[partOneIndex].compareTo(temp[partTwoIndex]) < 0) {
                    if (isAscending) {
                        arr[cur] = temp[partOneIndex];
                        partOneIndex++;
                    } else {
                        arr[cur] = temp[partTwoIndex];
                        partTwoIndex++;
                    }
                } else {
                    if (isAscending) {
                        arr[cur] = temp[partTwoIndex];
                        partTwoIndex++;
                    } else {
                        arr[cur] = temp[partOneIndex];
                        partOneIndex++;
                    }
                }
            } else if (partOneIndex > partOneBound) {
                arr[cur] = temp[partTwoIndex];
                partTwoIndex++;
            } else {
                arr[cur] = temp[partOneIndex];
                partOneIndex++;
            }
        }

    }

}

5、時(shí)間復(fù)雜度分析

  • 遞歸函數(shù)的粗略算法復(fù)雜度分析：利用遞歸樹(shù)，每個(gè)節(jié)點(diǎn)所包含的操作數(shù)之和。
歸并排序-時(shí)間復(fù)雜度分析

6、優(yōu)化

  • 優(yōu)化1：有些情況下，沒(méi)有必要merge。merge的含義是將“一個(gè)數(shù)組中的兩個(gè)有序部分合并”，如果遇到下面的情況：升序時(shí)當(dāng)“后部”的“第一個(gè)元素”就大于或等于“前部”的“最后一個(gè)元素”；降序時(shí)當(dāng)“后部”的“第一個(gè)元素”就小于或等于“前部”的“最后一個(gè)元素。這時(shí)，就足以判定當(dāng)前遞歸過(guò)程中的數(shù)組就已經(jīng)是有序的了，沒(méi)有必要再調(diào)用merge方法了。
import java.util.Arrays;

public class MergeSort {

    public static <E extends Comparable<E>> void mergeSort(E[] arr, boolean isAscending) {
        mergeSort(arr, 0, arr.length - 1, isAscending);
    }

    private static <E extends Comparable<E>> void mergeSort(E[] arr, int l, int r, boolean isAscending) {
        if (l >= r) {
            return;
        }
        int mid = (l + r) / 2;
        mergeSort(arr, l, mid, isAscending);
        mergeSort(arr, mid + 1, r, isAscending);
        
        // 優(yōu)化
        if (isAscending) {
            if (arr[mid].compareTo(arr[mid + 1]) > 0) {
                merge(arr, l, mid, r, isAscending);
            }
        } else {
            if (arr[mid].compareTo(arr[mid + 1]) < 0) {
                merge(arr, l, mid, r, isAscending);
            }
        }
    }

    private static <E extends Comparable<E>> void merge(E[] arr, int l, int mid, int r, boolean isAscending) {
        E[] temp = Arrays.copyOfRange(arr, l, r + 1);
        int partOneIndex = 0;
        int partOneBound = mid - l;
        int partTwoIndex = mid + 1 - l;
        int partTwoBound = r - l;

        for (int cur = l; cur <= r; cur++) {
            if (partOneIndex <= partOneBound && partTwoIndex <= partTwoBound) {
                if (temp[partOneIndex].compareTo(temp[partTwoIndex]) < 0) {
                    if (isAscending) {
                        arr[cur] = temp[partOneIndex];
                        partOneIndex++;
                    } else {
                        arr[cur] = temp[partTwoIndex];
                        partTwoIndex++;
                    }
                } else {
                    if (isAscending) {
                        arr[cur] = temp[partTwoIndex];
                        partTwoIndex++;
                    } else {
                        arr[cur] = temp[partOneIndex];
                        partOneIndex++;
                    }
                }
            } else if (partOneIndex > partOneBound) {
                arr[cur] = temp[partTwoIndex];
                partTwoIndex++;
            } else {
                arr[cur] = temp[partOneIndex];
                partOneIndex++;
            }
        }

    }

}
  • 優(yōu)化2：在滿足某種條件的時(shí)候，歸并排序不是最好的選擇。所以這次優(yōu)化的思路就是結(jié)合其他的排序算法。

歸并排序（O(nlogn)復(fù)雜度）的優(yōu)勢(shì)體現(xiàn)在數(shù)據(jù)規(guī)模大、越無(wú)序的情況。但是在數(shù)據(jù)已經(jīng)是有序的情況下，歸并排序反倒顯得沒(méi)有優(yōu)勢(shì)。
在執(zhí)行merge方法前進(jìn)行判斷的情況下（完成“優(yōu)化1”的歸并排序），對(duì)于有序的數(shù)組，時(shí)間復(fù)雜度“退化”為O(n)。
之所以要強(qiáng)調(diào)歸并排序在有序中沒(méi)有優(yōu)勢(shì)，是因?yàn)闅w并排序的編寫(xiě)采用的是遞歸，遞歸過(guò)程中會(huì)出現(xiàn)“小數(shù)組”的情況（比如只對(duì)兩個(gè)元素進(jìn)行排序），在數(shù)組規(guī)模的越小的情況下，出現(xiàn)“當(dāng)前數(shù)組本身已經(jīng)就是有序”的情況的概率越大。于是，將在當(dāng)前遞歸過(guò)程中“數(shù)組小”的時(shí)候采用“插入排序”。

插入排序與歸并排序在面對(duì)已經(jīng)是有序的數(shù)據(jù)的時(shí)候，時(shí)間復(fù)雜度均是O(n)，但是插入排序在復(fù)雜度的常量上（因?yàn)槊枋鰪?fù)雜度的時(shí)候，通常拋棄常量）

對(duì)插入排序代碼進(jìn)行一些改造：

    /**
     * 對(duì)數(shù)組 arr 中的索引 [l,r] 區(qū)間部分進(jìn)行“插入排序”
     */
    private static <E extends Comparable<E>> void insertionSort(E[] arr, int l, int r, boolean isAscending) {
        for (int i = l; i <= r; i++) {
            for (int j = i; j - 1 >= l; j--) {
                if (isAscending) {
                    if (arr[j].compareTo(arr[j - 1]) < 0) {
                        swap(arr, j, j - 1);
                    } else {
                        break;
                    }
                } else {
                    if (arr[j].compareTo(arr[j - 1]) > 0) {
                        swap(arr, j, j - 1);
                    } else {
                        break;
                    }
                }
            }
        }
    }

import java.util.Arrays;

public class MergeSort {

    public static <E extends Comparable<E>> void mergeSort(E[] arr, boolean isAscending) {
        mergeSort(arr, 0, arr.length - 1, isAscending);
    }

    private static <E extends Comparable<E>> void mergeSort(E[] arr, int l, int r, boolean isAscending) {
        // 優(yōu)化：當(dāng)數(shù)組規(guī)模較小的時(shí)候（長(zhǎng)度小于某個(gè)確定值的時(shí)候），采用插入排序
        if (r - l + 1 <= 4) {
            insertionSort(arr, l, r, isAscending);
            return;
        }

        int mid = (l + r) / 2;
        mergeSort(arr, l, mid, isAscending);
        mergeSort(arr, mid + 1, r, isAscending);

        // 優(yōu)化
        if (isAscending) {
            if (arr[mid].compareTo(arr[mid + 1]) > 0) {
                merge(arr, l, mid, r, isAscending);
            }
        } else {
            if (arr[mid].compareTo(arr[mid + 1]) < 0) {
                merge(arr, l, mid, r, isAscending);
            }
        }
    }

    private static <E extends Comparable<E>> void merge(E[] arr, int l, int mid, int r, boolean isAscending) {
        E[] temp = Arrays.copyOfRange(arr, l, r + 1);
        int partOneIndex = 0;
        int partOneBound = mid - l;
        int partTwoIndex = mid + 1 - l;
        int partTwoBound = r - l;

        for (int cur = l; cur <= r; cur++) {
            if (partOneIndex <= partOneBound && partTwoIndex <= partTwoBound) {
                if (temp[partOneIndex].compareTo(temp[partTwoIndex]) < 0) {
                    if (isAscending) {
                        arr[cur] = temp[partOneIndex];
                        partOneIndex++;
                    } else {
                        arr[cur] = temp[partTwoIndex];
                        partTwoIndex++;
                    }
                } else {
                    if (isAscending) {
                        arr[cur] = temp[partTwoIndex];
                        partTwoIndex++;
                    } else {
                        arr[cur] = temp[partOneIndex];
                        partOneIndex++;
                    }
                }
            } else if (partOneIndex > partOneBound) {
                arr[cur] = temp[partTwoIndex];
                partTwoIndex++;
            } else {
                arr[cur] = temp[partOneIndex];
                partOneIndex++;
            }
        }
    }

    /**
     * 對(duì)數(shù)組 arr 中的索引 [l,r] 區(qū)間部分進(jìn)行“插入排序”
     */
    private static <E extends Comparable<E>> void insertionSort(E[] arr, int l, int r, boolean isAscending) {
        for (int i = l; i <= r; i++) {
            for (int j = i; j - 1 >= l; j--) {
                if (isAscending) {
                    if (arr[j].compareTo(arr[j - 1]) < 0) {
                        swap(arr, j, j - 1);
                    } else {
                        break;
                    }
                } else {
                    if (arr[j].compareTo(arr[j - 1]) > 0) {
                        swap(arr, j, j - 1);
                    } else {
                        break;
                    }
                }
            }
        }
    }

    private static <E> void swap(E[] arr, int i, int j) {
        if (arr != null && i >= 0 && i < arr.length && j >= 0 && j < arr.length) {
            E temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }

}

該優(yōu)化并不一定適合所有編程語(yǔ)言，在一些的語(yǔ)言中，這樣的優(yōu)化甚至可能會(huì)起到反效果。

  • 優(yōu)化3：這個(gè)優(yōu)化屬于空間上的優(yōu)化。之前的merge方法中，都會(huì)創(chuàng)建一個(gè)新的數(shù)組temp，因?yàn)?code>merge方法是會(huì)被多次調(diào)用，所以數(shù)組temp也會(huì)被重復(fù)創(chuàng)建，不斷開(kāi)辟新的數(shù)組空間是不合適的。所以這個(gè)優(yōu)化所做的是，在整個(gè)歸并排序過(guò)程中，只采用的一個(gè)數(shù)組空間來(lái)輔助完成歸并排序。
import java.util.Arrays;

public class MergeSort {

    public static <E extends Comparable<E>> void mergeSort(E[] arr, boolean isAscending) {
        // 優(yōu)化，temp 將作為整個(gè)歸并排序中的唯一輔助
        // 這里 copyOfRange 不是必須的，只要 temp 是一個(gè)長(zhǎng)度與 arr  的長(zhǎng)度相同的即可，一個(gè)新 new 的數(shù)組也是可以的：E[] temp = (E[]) new Object[arr.length]
        E[] temp = Arrays.copyOfRange(arr, 0, arr.length);
        mergeSort(arr, 0, arr.length - 1, isAscending, temp);
    }

    private static <E extends Comparable<E>> void mergeSort(E[] arr, int l, int r, boolean isAscending, E[] temp) {
        if (l >= r) {
            return;
        }
        int mid = (l + r) / 2;
        mergeSort(arr, l, mid, isAscending, temp);
        mergeSort(arr, mid + 1, r, isAscending, temp);

        // 優(yōu)化
        if (isAscending) {
            if (arr[mid].compareTo(arr[mid + 1]) > 0) {
                merge(arr, l, mid, r, isAscending, temp);
            }
        } else {
            if (arr[mid].compareTo(arr[mid + 1]) < 0) {
                merge(arr, l, mid, r, isAscending, temp);
            }
        }
    }

    private static <E extends Comparable<E>> void merge(E[] arr, int l, int mid, int r, boolean isAscending, E[] temp) {
        // 優(yōu)化，不用再新創(chuàng)建 temp 數(shù)組，通過(guò)“拷貝”使 temp 與 arr 保持一致即可
        // arr[l~r] 與 temp[l~r] 保持一致
        System.arraycopy(arr, l, temp, l, r - l + 1);

        int partOneIndex = l;
        int partOneBound = mid;

        int partTwoIndex = mid + 1;
        int partTwoBound = r;

        for (int cur = l; cur <= r; cur++) {
            if (partOneIndex <= partOneBound && partTwoIndex <= partTwoBound) {
                if (temp[partOneIndex].compareTo(temp[partTwoIndex]) < 0) {
                    if (isAscending) {
                        arr[cur] = temp[partOneIndex];
                        partOneIndex++;
                    } else {
                        arr[cur] = temp[partTwoIndex];
                        partTwoIndex++;
                    }
                } else {
                    if (isAscending) {
                        arr[cur] = temp[partTwoIndex];
                        partTwoIndex++;
                    } else {
                        arr[cur] = temp[partOneIndex];
                        partOneIndex++;
                    }
                }
            } else if (partOneIndex > partOneBound) {
                arr[cur] = temp[partTwoIndex];
                partTwoIndex++;
            } else {
                arr[cur] = temp[partOneIndex];
                partOneIndex++;
            }
        }

    }

}

7、自底向上的歸并排序

  • 上面所編寫(xiě)的歸并排序的代碼，是“自頂向下”的。而“自底向上”的思想是開(kāi)始不將數(shù)組看成一個(gè)整體，而是直接就分組，由1個(gè)到2個(gè)再到4個(gè)······
歸并排序-自底向上-1
歸并排序-自底向上-2
歸并排序-自底向上-3
import java.util.Arrays;

public class MergeSort {

    public static <E extends Comparable<E>> void mergeSort(E[] arr, boolean isAscending) {
        E[] temp = Arrays.copyOfRange(arr, 0, arr.length);

        int n = arr.length;

        // 外層循環(huán)：自底向上過(guò)程中，歸并的尺寸
        // 1 -> 2 -> 4 -> 8 -> ······
        for (int size = 1; size < n; size += size) {
            // 內(nèi)層循環(huán)：待合并區(qū)間的起始位置 i
            // 合并：[i, i + size - 1] 與 [i + size, i + size + size - 1]
            for (int i = 0; i + size < n; i += (size + size)) {
                if (isAscending) {
                    if (arr[i + size - 1].compareTo(arr[i + size]) > 0) {
                        // Math.min(i + size + size - 1, n - 1) 的意義：“i + size + size - 1” 在排序到最后的時(shí)候會(huì)出現(xiàn)越界
                        merge(arr, i, i + size - 1, Math.min(i + size + size - 1, n - 1), true, temp);
                    }
                } else {
                    if (arr[i + size - 1].compareTo(arr[i + size]) < 0) {
                        merge(arr, i, i + size - 1, Math.min(i + size + size - 1, n - 1), false, temp);
                    }
                }
            }
        }

    }

    private static <E extends Comparable<E>> void merge(E[] arr, int l, int mid, int r, boolean isAscending, E[] temp) {
        // 優(yōu)化
        System.arraycopy(arr, l, temp, l, r - l + 1);

        int partOneIndex = l;
        int partOneBound = mid;

        int partTwoIndex = mid + 1;
        int partTwoBound = r;

        for (int cur = l; cur <= r; cur++) {
            if (partOneIndex <= partOneBound && partTwoIndex <= partTwoBound) {
                if (temp[partOneIndex].compareTo(temp[partTwoIndex]) < 0) {
                    if (isAscending) {
                        arr[cur] = temp[partOneIndex];
                        partOneIndex++;
                    } else {
                        arr[cur] = temp[partTwoIndex];
                        partTwoIndex++;
                    }
                } else {
                    if (isAscending) {
                        arr[cur] = temp[partTwoIndex];
                        partTwoIndex++;
                    } else {
                        arr[cur] = temp[partOneIndex];
                        partOneIndex++;
                    }
                }
            } else if (partOneIndex > partOneBound) {
                arr[cur] = temp[partTwoIndex];
                partTwoIndex++;
            } else {
                arr[cur] = temp[partOneIndex];
                partOneIndex++;
            }
        }

    }

}
最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書(shū)系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容