排序算法 - 归并排序(Merge Sort)

by LauCyun Aug 01,2014 22:58:57 3,832 views

核心:将两个有序对数组归并成一个更大的有序数组。通常做法为递归排序,并将两个不同的有序数组归并到第三个数组中。

先来看看图1,归并排序是一种典型的分治应用。

图1 归并排序

迭代法

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

递归法

原理如下(假设序列共有n个元素):

  1. 将序列每相邻两个数字进行归并操作,形成\({\displaystyle floor(n/2)}\)个序列,排序后每个序列包含两个元素
  2. 将上述序列再次归并,形成\({\displaystyle floor(n/4)}\)个序列,每个序列包含四个元素
  3. 重复步骤2,直到所有元素排序完毕

 

算法实现

C

迭代法:

#include <stdio.h>
#include <stdlib.h>

#define ElemType int

void printArray(ElemType *, const int);
int min(ElemType, ElemType);
void mergeSort(ElemType arr[], int len);


int min(ElemType x, ElemType y) {
    return x < y ? x : y;
}

void mergeSort(ElemType arr[], int len) {
    ElemType *a = arr;
    ElemType *b = (ElemType *) malloc(len * sizeof(int));
    int seg, start;
    for (seg = 1; seg < len; seg += seg) {
        for (start = 0; start < len; start += seg + seg) {
            int low = start, mid = min(start + seg, len), high = min(start + seg + seg, len);
            int k = low;
            int start1 = low, end1 = mid;
            int start2 = mid, end2 = high;
            while (start1 < end1 && start2 < end2)
                b[k++] = a[start1] < a[start2] ? a[start1++] : a[start2++];
            while (start1 < end1)
                b[k++] = a[start1++];
            while (start2 < end2)
                b[k++] = a[start2++];
        }
        int *temp = a;
        a = b;
        b = temp;
//        printArray(a, len);
    }
    if (a != arr) {
        int i;
        for (i = 0; i < len; i++)
            b[i] = a[i];
        b = a;
    }
    free(b);
}

void printArray(ElemType *array, const int len) {
    for (int i = 0; i < len; i++) {
        printf("%-4d", array[i]);
    }
    printf("\n");
}

int main(int argc, char *argv[]) {
    ElemType a[8] = {6, 5, 3, 1, 8, 7, 2, 4};
    printArray(a, 8);
    mergeSort(a, 8);
    printArray(a, 8);
    return 0;
}

递归法:

#include <stdio.h>

#define ElemType int

void mergeSortRecursive(ElemType arr[], ElemType reg[], int start, int end);
void mergeSort(ElemType arr[], const int len);
void printArray(ElemType *, const int);

void mergeSortRecursive(ElemType arr[], ElemType reg[], int start, int end) {
    if (start >= end)
        return;

    int len = end - start, mid = (len >> 1) + start;
    int start1 = start, end1 = mid;
    int start2 = mid + 1, end2 = end;
    mergeSortRecursive(arr, reg, start1, end1);
    mergeSortRecursive(arr, reg, start2, end2);
    int k = start;
    while (start1 <= end1 && start2 <= end2)
        reg[k++] = arr[start1] < arr[start2] ? arr[start1++] : arr[start2++];
    while (start1 <= end1)
        reg[k++] = arr[start1++];
    while (start2 <= end2)
        reg[k++] = arr[start2++];
    for (k = start; k <= end; k++)
        arr[k] = reg[k];
}

void mergeSort(ElemType arr[], const int len) {
    ElemType reg[len];
    mergeSortRecursive(arr, reg, 0, len - 1);
}

void printArray(ElemType *array, const int len) {
    for (int i = 0; i < len; i++) {
        printf("%-4d", array[i]);
    }
    printf("\n");
}

int main(int argc, char *argv[]) {
    ElemType a[8] = {6, 5, 3, 1, 8, 7, 2, 4};
    Show(a, 8);
    mergeSort(a, 8);
    Show(a, 8);
    return 0;
}

C++

#include<iostream>

using namespace std;
const int N = 8;
using ElemType = int;

bool MergeSort(ElemType *array, int n);
void ArraySort(ElemType *array, int first, int last, ElemType *temp);
void MergeArray(ElemType *array, int first, int mid, int last, ElemType *temp);
void Show(ElemType *array);

bool MergeSort(int a[], int n) {
    ElemType *p = new int[n];
    if (p == NULL) {
        return false;
    }
    ArraySort(a, 0, n - 1, p);
    delete[] p;
    return true;
}

void ArraySort(ElemType *array, int first, int last, ElemType *temp) {
    if (first < last) {
        int mid = (first + last) / 2;
        ArraySort(array, first, mid, temp);    //左边有序
        ArraySort(array, mid + 1, last, temp); //右边有序
        MergeArray(array, first, mid, last, temp); //再将二个有序数列合并
    }
}

//将有二个有序数列a[first...mid]和a[mid...last]合并。
void MergeArray(ElemType *array, int first, int mid, int last, ElemType *temp) {
    int i = first, j = mid + 1;
    int m = mid, n = last;
    int k = 0;
    while (i <= m && j <= n) {
        if (array[i] <= array[j])
            temp[k++] = array[i++];
        else
            temp[k++] = array[j++];
    }
    while (i <= m)
        temp[k++] = array[i++];
    while (j <= n)
        temp[k++] = array[j++];
    for (i = 0; i < k; i++)
        array[first + i] = temp[i];
    Show(array);
}

void Show(ElemType *array) {
    for (int i = 0; i < N; i++) {
        printf("%-4d", array[i]);
    }
    cout << endl;
}

int main() {
    ElemType array[N] = {6, 5, 3, 1, 8, 7, 2, 4};
    cout << "排序前:" << endl;
    Show(array);
    cout << "排序过程:" << endl;
    MergeSort(array, N);
    cout << "排序结果:" << endl;
    Show(array);
    return 0;
}

Python

#!/usr/bin/env python
# -*- coding: utf-8 -*-


class Sort:
    def mergeSort(self, alist):
        if len(alist) <= 1:
            return alist

        mid = int(len(alist) / 2)
        left = self.mergeSort(alist[:mid])
        #print("left = " + str(left))
        right = self.mergeSort(alist[mid:])
        #print("right = " + str(right))
        return self.mergeSortedArray(left, right)

    # @param A and B: sorted integer array A and B.
    # @return: A new sorted integer array
    def mergeSortedArray(self, A, B):
        sortedArray = []
        l = 0
        r = 0
        while l < len(A) and r < len(B):
            if A[l] < B[r]:
                sortedArray.append(A[l])
                l += 1
            else:
                sortedArray.append(B[r])
                r += 1
        sortedArray += A[l:]
        sortedArray += B[r:]

        return sortedArray


unsortedArray = [6, 5, 3, 1, 8, 7, 2, 4]
merge_sort = Sort()
print(merge_sort.mergeSort(unsortedArray))

 

算法过程演示

如果显示不正常,请戳这里

 

复杂度分析

最好、最坏和平均的时间性能都为:\(O{\displaystyle (nlogn)}\)

空间复杂度为:\(O(n)\)

比较操作的次数介于\({\displaystyle (nlogn)/2}\)\({\displaystyle nlogn-n+1}\)

赋值操作的次数是\({\displaystyle (2nlogn)}\)

归并排序比较占用内存,但却是一种效率高且稳定的算法。

 

参考文档

(全文完)

Tags