八大排序算法之归并排序

基本思想

归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。

算法的实现

package com.zyg.sort;

public class MergeSortAlgorithm
{
    // 归并排序
    public static void mergeSort(int a[], int left, int right)
    {
        if (left < right)
        {
            // 获取中间节点
            int mid = (left + right) / 2;
            // 左边部分归并排序
            <!--more-->
            mergeSort(a, left, mid);
            // 右边部分归并排序
            mergeSort(a, mid + 1, right);
            // 合并归并后的数组
            merge(a, left, mid, right);
        }
    }
    
    public static void merge(int a[], int left, int mid, int right)
    {
        // 数组长度
        int len = a.length;
        // 定义一个临时数组
        int temp[] = new int[len];
        int index = left, i = left, j = mid + 1;
        // 临时数组复制
        for (int k = 0; k < len; k++)
        {
            temp[k] = a[k];
        }
        while (i <= mid && j <= right)
        {
            // 找出临时数组中左右部分中较小的元素赋给数组a
            if (temp[i] < temp[j])
                a[index++] = temp[i++];
            else
                a[index++] = temp[j++];
        }
        // 如果临时数组左边有剩余，则将剩余部分赋给数组a
        if (i <= mid)
            a[index++] = temp[i++];
        // 如果临时数组右边有剩余，则将剩余部分赋给数组a
        if (j <= right)
            a[index++] = temp[j++];
    }
    
    // 打印数组
    public static void printArray(int a[])
    {
        for (int i = 0; i < a.length; i++)
        {
            System.out.println(a[i]);
        }
    }
    
    public static void main(String[] args)
    {
        // 定义初始化数组
        int a[] =
        { 4, 3, 6, 7, 33, 15, 90, 65 };
        // 进行归并排序
        mergeSort(a, 0, a.length - 1);
        // 打印数组
        printArray(a);
    }
}

效率

时间复杂度

平均情况：O(nlog₂n)
最好情况：O(nlog₂n)
最坏情况：O(n²)

空间复杂度

O(n)

稳定性

稳定