归并排序

1. 归并排序

1.1. 归并

归并是指将两个元素序列合并为一个有序元素序列的操作。

1.2. 原理

假设有一个乱序的元素序列,对其进行归并排序:

首先将该元素序列分割为两个子元素序列(方便起见我们可以将由任何一次分割得到的两个元素序列称为左序列右序列),随后再对左序列进行分割,得到下一级的(更小的)左序列和右序列……经过不断重复,最终会得到只包含一个元素的左序列。

此时不再对左序列进行分割,而是开始将当前一级的左序列和与其对应的右序列进行合并,而合并所得到的有序的元素序列又正好是上一级的左序列,之后再经过多次这样的合并操作,最终会使得最初的元素序列变为有序。

2. JAVA 实现

归并排序一般由递归实现,以下是 JAVA 实现归并排序的内容:

import java.util.Random;

public class MergeSort {
    public static void main(String[] args) {
        int[] sortArray = generateRandomeArray();
        int length = sortArray.length;
        mergeSort(sortArray, 0, length - 1);
        for (int i : sortArray) {
            System.out.println(i);
        }
    }

    /* 生成一组随机数 */
    public static int[] generateRandomeArray() {
        int[] randomArray = new int[10];
        Random random = new Random();
        for (int i = 0; i < 10; i++) {
            randomArray[i] = random.nextInt(100);
        }
        return randomArray;
    }

    public static void mergeSort(int[] sortArray, int headPointer, int tailPointer) {
        /* 若头指针与尾指针相等, 则递归开始返回 */
        if (headPointer < tailPointer) {
            int middlePointer = (headPointer + tailPointer) / 2;
            mergeSort(sortArray, headPointer, middlePointer);
            mergeSort(sortArray, middlePointer + 1, tailPointer);
            merge(sortArray, headPointer, middlePointer, tailPointer);
        }
    }

    public static void merge(int[] sortArray, int headPointer, int middlePointer, int tailPointer) {
        int leftArrayCount = middlePointer - headPointer + 1;
        int rightArrayCount = tailPointer - middlePointer;
        int[] leftArray = new int[leftArrayCount];  // 创建两个临时数组
        int[] rightArray = new int[rightArrayCount];
        int i, j, k;
        /* 将 sortArray 中的元素按照顺序分别存入上述两数组 */
        k = headPointer;
        for (i = 0; i < leftArrayCount; i++, k++) {
            leftArray[i] = sortArray[k];
        }
        for (j = 0; j < rightArrayCount; j++, k++) {
            rightArray[j] = sortArray[k];
        }
        /* 比较以上两数组的各个元素, 按照大小顺序放入 sortArray */
        k = headPointer;
        for (i = j = 0; i < leftArrayCount && j < rightArrayCount; k++) {
            if (leftArray[i] < rightArray[j]) {
                sortArray[k] = leftArray[i];
                i++;
            } else {
                sortArray[k] = rightArray[j];
                j++;
            }
        }
        /* 将 leftArray 或 rightArray 中剩余的元素放入 sortArray */
        if (i < leftArrayCount) {
            int leftTimes = leftArrayCount - i;
            while (leftTimes > 0) {
                sortArray[k++] = leftArray[i++];
                leftTimes--;
            }
        } else if (j < rightArrayCount) {
            int leftTimes = rightArrayCount - j;
            while (leftTimes > 0) {
                sortArray[k++] = rightArray[j++];
                leftTimes--;
            }            
        }
    }
}
2019-2020 @lukbash