体育彩票销售站联盟

归并排序

不求上进的咸鱼2018-12-05 13:06:42

归并排序(英语:Merge sort,或mergesort),是建立在归并操作上的一种有效的排序算法(https://zh.wikipedia.org/wiki/%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95),效率为O(nlogn)(大O符号)(https://zh.wikipedia.org/wiki/%E5%A4%A7O%E7%AC%A6%E5%8F%B7)。1945年由约翰·冯·诺伊曼(https://zh.wikipedia.org/wiki/%E7%BA%A6%E7%BF%B0%C2%B7%E5%86%AF%C2%B7%E8%AF%BA%E4%BC%8A%E6%9B%BC)首次提出。该算法是采用分治法(Divide and Conquer)(https://zh.wikipedia.org/wiki/%E5%88%86%E6%B2%BB%E6%B3%95)的一个非常典型的应用,且各层分治递归可以同时进行。



C++实现

#include<cstdio>

#include<iostream>

#include<algorithm>

using namespace std;

const int N = 1e6;

int arr1[N];

int arr2[N];

int arr3[(N<<1)+10];

int n;

void conquer(int left,int mid,int right)

{

    int i=left,j=mid+1;

    int k=0;

    for(; i<=mid&&j<=right;)

    {

        if(arr1[i]<arr1[j])

            arr2[k++]=arr1[i++];

        else

            arr2[k++]=arr1[j++];

    }

    while(i<=mid)

        arr2[k++]=arr1[i++];

    while(j<=right)

        arr2[k++]=arr1[j++];

    for(int l=0; l<k; ++l)

        arr1[left+l]=arr2[l];//数组是从left到right,并非0到k

}

void divide(int left,int right)

{

    if(left<right)

    {

        int mid = (left+right)>>1;

        divide(left,mid);

        divide(mid+1,right);

        conquer(left,mid,right);

    }

}

int main()

{

    scanf("%d",&n);

    for(int i=0; i<n; ++i)

        scanf("%d",arr1+i);

    divide(0,n-1);

    for(int i=0; i<n; ++i)

        printf("%d ",arr1[i]);

    return 0;

}




JavaScript实现

 function mergeSort(array) {
    function sort(array, first, last) {
        first = (first === undefined) ? 0 : first
        last = (last === undefined) ? array.length - 1 : last
        if (last - first < 1) {
            return;
        }
        var middle = Math.floor((first + last) / 2);
        sort(array, first, middle);
        sort(array, middle + 1, last);
        var f = first,
            m = middle,
            i,
            temp;
        while (f <= m && m + 1 <= last) {
            if (array[f] >= array[m + 1]) { // 这里使用了插入排序的思想
                temp = array[m + 1];
                for (i = m; i >= f; i--) {
                    array[i + 1] = array[i];
                }
                array[f] = temp;
                m++
            } else {
                f++
            }
        }
        return array;
    }
    return sort(array);
}

http://bubkoo.com/2014/01/15/sort-algorithm/merge-sort/



算法分析

(1)稳定性
      归并排序是一种稳定的排序。

(2)存储结构要求
     可用顺序存储结构。也易于在链表上实现。

(3)时间复杂度
     对长度为n的文件,需进行 趟二路归并,每趟归并的时间为O(n),故其时间复杂度无论是在最好情况下还是在最坏情况下均是O(nlgn)

(4)空间复杂度
     需要一个辅助向量来暂存两有序子文件归并的结果,故其辅助空间复杂度为O(n)

不求上进的咸鱼