归并排序.md

归并排序

简介

将数组分成左右两部分, 左边部分排好序, 右边部分排好序, 然后左右两部分利用类似外排的方式进行归并

代码

PHP

<?php

class MergeSort
{
    /**
     * 归并排序
     *
     * @param $arr
     * @param $left
     * @param $right
     */
    public static function sort(&$arr, $left, $right)
    {
        if ($left == $right) {
            return;
        }

        $mid = floor(($left + $right) / 2);
        self::sort($arr, $left, $mid);
        self::sort($arr, $mid + 1, $right);
        self::merge($arr, $left, $mid, $right);
    }

    /**
     * 归并
     *
     * @param $arr
     * @param $left
     * @param $mid
     * @param $right
     */
    public static function merge(&$arr, $left, $mid, $right)
    {
        $p1 = $left;
        $p2 = $mid + 1;
        $help = [];

        while ($p1 <= $mid && $p2 <= $right) {
            $help[] = $arr[$p1] < $arr[$p2] ? $arr[$p1++] : $arr[$p2++];
        }

        while ($p1 <= $mid) {
            $help[] = $arr[$p1++];
        }
        while ($p2 <= $right) {
            $help[] = $arr[$p2++];
        }

        for ($i = 0; $i < count($help); $i++) {
            $arr[$left + $i] = $help[$i];
        }
    }
}

// Test
$arr = [4, 3, 2, 1];
MergeSort::sort($arr, 0, count($arr) - 1);
// [1, 2, 3, 4]
print_r($arr);

java

import java.util.Arrays;

public class MergeSort {
	/**
	 * 归并排序
	 * @param arr
	 * @param left
	 * @param right
	 */
	public static void mergeSort(int[] arr, int left, int right) {
		if (left == right) {
			return;
		}
		int mid = (left + right) / 2;
		// 左半部分排序
		mergeSort(arr, left, mid);
		// 右半部分排序
		mergeSort(arr, mid + 1, right);
		merge(arr, left, mid, right);
	}
	
	/**
	 * 把两个有序数组合并成一个有序数组
	 * @param arr
	 * @param left
	 * @param mid
	 * @param right
	 */
	public static void merge(int[] arr, int left, int mid, int right) {
		int[] help = new int[right - left + 1];
		int i = 0;
		int p1 = left;
		int p2 = mid + 1;
		while (p1 <= mid && p2 <= right) {
			help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
		}
		
		// 左半部分数组没有越界
		while (p1 <= mid) {
			help[i++] = arr[p1++];
		}
		// 右半部分没有越界 
		while (p2 <= right) {
			help[i++] = arr[p2++];
		}
		
		for (i = 0; i < help.length; i++) {
			arr[left + i] = help[i];
		}
	}
	
	public static void main(String[] args) {
		int[] arr = {4, 3, 2, 1};
		mergeSort(arr, 0, arr.length - 1);
		System.out.println(Arrays.toString(arr));
	}
}

时间复杂度

根据 递归行为的实质和递归行为时间复杂度的计算

T(N) = a*T(N/b) + O(N^d)
T(N) = 2*T(N/2) + O(N) // O(N)是因为p1和p2指针合起来需要遍历整个数组
所以, a=2, b=2, d=1
根据, log(b,a) = d 复杂度为O(N^d * logN)
所以, 归并排序的时间复杂度为: O(N*logN)