每日一题之归并排序

归并排序

1、归并排序原理

归并排序（Merge Sort）是建立在归并操作上的一种有效，稳定的排序算法，该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

简单来说就是把数组从中间划分为两个子数组，一直递归地把子数组划分成更小的数组，直到子数组里面只有一个元素的时候开始排序。排序的方法就是按照大小顺序合并两个元素。接着依次按照递归的顺序返回，不断合并排好序的数组，直到把整个数组排好序。

2、归并排序的步骤

3、归并排序的代码演示

• java

import java.util.Scanner;

public class Main {
    private static int[] tmp = new int[100010];

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] nums = new int[n];
        for (int i = 0; i < n; ++i) {
            nums[i] = sc.nextInt();
        }
        mergeSort(nums, 0, n - 1);
        for (int i = 0; i < n; ++i) {
            System.out.printf("%d ", nums[i]);
        }
    }

    public static void mergeSort(int[] nums, int left, int right) {
        if (left >= right) {
            return;
        }
        int mid = (left + right) >>> 1;
        mergeSort(nums, left, mid);
        mergeSort(nums, mid + 1, right);
        int i = left, j = mid + 1, k = 0;
        while (i <= mid && j <= right) {
            if (nums[i] <= nums[j]) {
                tmp[k++] = nums[i++];
            } else {
                tmp[k++] = nums[j++];
            }
        }
        while (i <= mid) {
            tmp[k++] = nums[i++];
        }
        while (j <= right) {
            tmp[k++] = nums[j++];
        }
        for (i = left, j = 0; i <= right; ++i, ++j) {
            nums[i] = tmp[j];
        }
    }
}

• C++

#include <iostream>
#include <vector>

using namespace std;

void printvec( const vector<int> &vec, const string &strbegin = "", const string &strend = "" )
{
    cout << strbegin << endl;
    for ( auto val : vec )
    {
        cout << val << "\t";
    }

    cout << endl;
    cout << strend << endl;
}


void mergesort( vector<int> & vec, int left, int right )
{
    if ( left >= right )
    {
        return;
    }

    int mid = left + (right - left) / 2;
    mergesort( vec, left, mid );
    mergesort( vec, mid + 1, right );

    int i = left;
    int j = mid + 1;
    int k = 0;
    vector<int>	vecTmp;
    while ( i <= mid && j <= right )
    {
        if ( vec[i] < vec[j] )
        {
            vecTmp.push_back( vec[i] );
            i++;
        }else  {
            vecTmp.push_back( vec[j] );
            j++;
        }
    }

    while ( i <= mid )
    {
        vecTmp.push_back( vec[i] );
        i++;
    }

    while ( j <= right )
    {
        vecTmp.push_back( vec[j] );
        j++;
    }

    for ( int i = left; i <= right; i++ )
    {
        vec[i] = vecTmp[i - left];
    }

    return;
}


int main( void )
{
    vector<int> vec = { 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 };
    printvec( vec );
    mergesort( vec, 0, vec.size() - 1 );
    printvec( vec, "after insert sort" );
    return(0);
}

• 作者测试

@Test
public void merge_sort() {
    int[] str={9,8,7,6,5,4,3,2,1,0};
    int rigth=str.length-1;
    sort(str);
    for (int i : str) {
        System.out.println(i);
    }
}

public static void sort(int []arr){
    int []temp = new int[arr.length];//在排序前，先建好一个长度等于原数组长度的临时数组，避免递归中频繁开辟空间
    sort(arr,0,arr.length-1,temp);
}

private static void sort(int[] arr,int left,int right,int []temp){
    if(left<right){
        int mid = (left+right)/2;
        sort(arr,left,mid,temp);//左边归并排序，使得左子序列有序
        sort(arr,mid+1,right,temp);//右边归并排序，使得右子序列有序
        mergeSort(arr,left,mid,right,temp);//将两个有序子数组合并操作
    }
}

public static void mergeSort(int[] nums, int left,int mid, int right,int[] temp) {
    int i=left,j=mid+1,k=0;
    while (i<=mid && j<=right) {
        if(nums[j]>=nums[i]) {
            temp[k++]=nums[i++];
        } else {
            temp[k++]=nums[j++];
        }
    }
    while (i <= mid) {
        temp[k++] = nums[i++];
    }
    while (j <= right) {
        temp[k++] = nums[j++];
    }
    for (i = left, j = 0; i <= right; ++i, ++j) {
        nums[i] = temp[j];
    }
}

4、归并排序的算法分析

归并排序是稳定排序，它也是一种十分高效的排序，能利用完全二叉树特性的排序一般性能都不会太差。java中Arrays.sort()采用了一种名为TimSort的排序算法，就是归并排序的优化版本。从上文的图中可看出，每次合并操作的平均时间复杂度为O(n)，而完全二叉树的深度为|log2n|。总的平均时间复杂度为O(nlogn)。而且，归并排序的最好，最坏，平均时间复杂度均为O(nlogn)。