归并排序 merge sort

归并排序

时间复杂度：平均、最好、最坏都是O(nlogn)
空间复杂度：O(n)
稳定性：稳定

算法解析

• 归并排序是使用了归并的思想，归并是将两个有序序列合到一个序列并使其有序
• 同时归并排序也使用了分治思想
• 归并排序分为 从上到下 和 从下到上 两种方式

算法描述（来源于百度）

归并操作的工作原理如下：

• 第一步：申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
• 第二步：设定两个指针，最初位置分别为两个已经排序序列的起始位置
• 第三步：比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
• 重复步骤3直到某一指针超出序列尾
• 将另一序列剩下的所有元素直接复制到合并序列尾

图片解析：

merge.jpg

上图已经很清楚了解释了归并排序的步骤及思路！如果还觉得不清晰，看下动画演示。

动画演示：

mergeSort.gif

一、从上到下的方式实现

c实现

void mergeSort(int *arr,int s,int mid,int e) {
    int *tmp = (int *)malloc((e-s+1)*sizeof(int));
    int i = s;
    int j = mid+1;
    int k = 0;
    while (i<=mid && j<=e) {
        if (arr[i] < arr[j]) {
            tmp[k++] = arr[i++];
        } else {
            tmp[k++] = arr[j++];
        }
    }
    while (i<=mid) {
        tmp[k++] = arr[i++];
    }
    while (j<=e) {
        tmp[k++] = arr[j++];
    }
    for (int l = 0; l<k; l++) {
        arr[l+s] = tmp[l];
    }
    free(tmp);
    tmp = NULL;
}

void merge(int *arr,int s,int e) {
    if (arr == NULL || s >= e) { return; }
    int mid = (s+e)/2;
    merge(arr, s, mid);
    merge(arr, mid+1, e);
    mergeSort(arr, s, mid, e);
}

OC实现

void mergeSort(NSMutableArray *arr,int s,int mid,int e) {
    NSMutableArray *arrM = [NSMutableArray array];
    int i = s;
    int j = mid + 1;
    while (i<=mid && j <= e) {
        if ([arr[i] intValue] <= [arr[j] intValue]) {
            [arrM addObject:arr[i++]];
        } else {
            //k+=(mid-i+1);逆序数
            [arrM addObject:arr[j++]];
        }
    }
    
    while (i<=mid) {
        [arrM addObject:arr[i++]];
    }
    while (j<=e) {
        [arrM addObject:arr[j++]];
    }
    for (int k = 0; k<arrM.count; k++) {
        arr[k+s] = arrM[k];
    }
}

void merge(NSMutableArray *arr,int s,int e) {
    if (s >= e) { return; }
    int mid = (s+e)/2;
    merge(arr, s, mid);
    merge(arr, mid+1, e);
    mergeSort(arr, s, mid, e);
}

Swift实现

func mergeSort(arr:inout [Int],start:Int,end:Int) -> Void {
    if arr.count == 0 || start >= end { return }
    let mid = (start+end)/2;
    mergeSort(arr: &arr, start: start, end: mid)
    mergeSort(arr: &arr, start: mid+1, end: end)
    //归并
    merge(arr: &arr, start: start, mid: mid, end: end)
}

func merge(arr:inout [Int],start:Int,mid:Int,end:Int) -> Void {
    if arr.count == 0 || start >= end { return }
    var tmp = Array.init(repeating: 0, count: end-start+1)
    var i = start
    var j = mid+1
    var k = 0
    while i <= mid && j <= end {
        if arr[i] <= arr[j] {
            tmp[k] = arr[i]
            i+=1
        } else {
            tmp[k] = arr[j]
            j+=1
        }
        k+=1
    }
    //把剩余的加进来
    while i<=mid {
        tmp[k] = arr[i]
        i+=1
        k+=1
    }
    while j<=end {
        tmp[k] = arr[j]
        j+=1
        k+=1
    }
    for l in 0..<k {
        arr[l+start] = tmp[l]
    }
}

以下实现均来源于网络，未验证

js实现

function mergeSort(arr) {  // 采用自上而下的递归方法
    var len = arr.length;
    if(len < 2) {
        return arr;
    }
    var middle = Math.floor(len / 2),
        left = arr.slice(0, middle),
        right = arr.slice(middle);
    return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right)
{
    var result = [];

    while (left.length && right.length) {
        if (left[0] <= right[0]) {
            result.push(left.shift());
        } else {
            result.push(right.shift());
        }
    }

    while (left.length)
        result.push(left.shift());

    while (right.length)
        result.push(right.shift());

    return result;
}

Python 代码实现

def mergeSort(arr):
    import math
    if(len(arr)<2):
        return arr
    middle = math.floor(len(arr)/2)
    left, right = arr[0:middle], arr[middle:]
    return merge(mergeSort(left), mergeSort(right))

def merge(left,right):
    result = []
    while left and right:
        if left[0] <= right[0]:
            result.append(left.pop(0));
        else:
            result.append(right.pop(0));
    while left:
        result.append(left.pop(0));
    while right:
        result.append(right.pop(0));
    return result

go实现

func mergeSort(arr []int) []int {
    length := len(arr)
    if length < 2 {
        return arr
    }
    middle := length / 2
    left := arr[0:middle]
    right := arr[middle:]
    return merge(mergeSort(left), mergeSort(right))
}

func merge(left []int, right []int) []int {
    var result []int
    for len(left) != 0 && len(right) != 0 {
        if left[0] <= right[0] {
            result = append(result, left[0])
            left = left[1:]
        } else {
            result = append(result, right[0])
            right = right[1:]
        }
    }

    for len(left) != 0 {
        result = append(result, left[0])
        left = left[1:]
    }

    for len(right) != 0 {
        result = append(result, right[0])
        right = right[1:]
    }

    return result
}

Java 代码实现

public class MergeSort implements IArraySort {

    @Override
    public int[] sort(int[] sourceArray) throws Exception {
        // 对 arr 进行拷贝，不改变参数内容
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

        if (arr.length < 2) {
            return arr;
        }
        int middle = (int) Math.floor(arr.length / 2);

        int[] left = Arrays.copyOfRange(arr, 0, middle);
        int[] right = Arrays.copyOfRange(arr, middle, arr.length);

        return merge(sort(left), sort(right));
    }

    protected int[] merge(int[] left, int[] right) {
        int[] result = new int[left.length + right.length];
        int i = 0;
        while (left.length > 0 && right.length > 0) {
            if (left[0] <= right[0]) {
                result[i++] = left[0];
                left = Arrays.copyOfRange(left, 1, left.length);
            } else {
                result[i++] = right[0];
                right = Arrays.copyOfRange(right, 1, right.length);
            }
        }

        while (left.length > 0) {
            result[i++] = left[0];
            left = Arrays.copyOfRange(left, 1, left.length);
        }

        while (right.length > 0) {
            result[i++] = right[0];
            right = Arrays.copyOfRange(right, 1, right.length);
        }
        return result;
    }
}

PHP 代码实现

function mergeSort($arr)
{
    $len = count($arr);
    if ($len < 2) {
        return $arr;
    }
    $middle = floor($len / 2);
    $left = array_slice($arr, 0, $middle);
    $right = array_slice($arr, $middle);
    return merge(mergeSort($left), mergeSort($right));
}

function merge($left, $right)
{
    $result = [];

    while (count($left) > 0 && count($right) > 0) {
        if ($left[0] <= $right[0]) {
            $result[] = array_shift($left);
        } else {
            $result[] = array_shift($right);
        }
    }

    while (count($left))
        $result[] = array_shift($left);

    while (count($right))
        $result[] = array_shift($right);
    return $result;
}