合并排序


难度级别 中等
经常问 亚马逊 Apple 回旋镖商业 高盛 杂货店 微软 神谕 Paytm 高通公司 Snapdeal Target公司
分而治之 排序

什么是合并排序?

合并排序递归程序。 这也是 分而治之 算法。 现在我们需要知道什么是分而治之算法? 这是一种过程,其中我们将问题划分为子问题,然后将其划分为找到最短的已解决子问题。 通过合并最短的已解决子问题,我们找到了解决主要/主要问题的解决方案。 让我们来看看 算法 用于merge_sort。

算法

步骤:1 将问题分为2个子问题。

步骤:2 子问题递归调用,直到达到最小大小(已解决子问题)。

步骤:3 合并已解决的子问题。

现在,转到以下示例 了解此算法的工作原理?

解释 合并排序

让我们假设一个数组A包含N个未排序的数字。 A = {9,1,4,2,5,3,7,2,6,17}

合并排序

合并排序

合并排序

合并排序

合并排序

合并排序

在第8步中,我们得到了最终结果 排序数组 使用merge_sort算法。

合并排序的实现 

/*C++ Implementation of Merge Sort*/ 
#include<bits/stdc++.h>
#define max_v 100000
using namespace std;
void add_subproblems(int a[],int l,int mid,int r)
{
    int start_1=l;//starting index of subproblem 1;
    int start_2=mid+1;//strating index of subproblem 2;
    int store=l;//used to store the no in array a with O(1) space complexity. 
    /*compare the element from begining of both subproblems and choose the minimum element from them
      and increment the index wrt minimum value by 1.*/
    while(start_1<=mid&&start_2<=r)
    {
        if((a[start_1]%max_v)<=(a[start_2]%max_v))
        {
            a[store]+=(a[start_1]%max_v)*max_v;
            store++;
            start_1++;
        }
        else
        {
            a[store]+=(a[start_2]%max_v)*max_v;
            store++;
            start_2++;
        }
    }
    /*if some elements are remaining in subproblem 1*/
    while(start_1<=mid)
    {
        a[store]+=(a[start_1]%max_v)*max_v;
        store++;
        start_1++; 
    }
    /*if some elements are remaining in subproblem 2*/
    while(start_2<=r)
    {
        a[store]+=(a[start_2]%max_v)*max_v;
        store++;
        start_2++;
    }
    /*now change the elements into their oroginal values*/
    for(int i=l;i<=r;i++)
    {
        a[i]/=max_v;
    }
}
void merge(int a[],int l,int r)
{
    if(l<r)
    {
        int mid=(l+r)/2;
        merge(a,l,mid);
        merge(a,mid+1,r);
        add_subproblems(a,l,mid,r);
    }
}
int main() 
{ 
    int number;
    /*total numbers which we want to sort*/
    cin>>number;
    int a[number];
    /*take input*/
    for(int i=0;i<number;i++)
    {
        cin>>a[i];
    }
    cout<<"Array before sorting: ";
    /*print the array*/
    for(int i=0;i<number;i++)
    {
        cout<<a[i]<<" ";
    }
    cout<<"\n";
    /*call merge function*/
    merge(a,0,number-1);
    cout<<"Array after sorting: ";
    /*print the array*/
    for(int i=0;i<number;i++)
    {
        cout<<a[i]<<" ";
    }
    cout<<"\n";
    return 0; 
}
10
9 1 4 2 5 3 7 2 6 17
Array before sorting: 9 1 4 2 5 3 7 2 6 17 
Array after sorting: 1 2 2 3 4 5 6 7 9 17

时间复杂度

O(N * log N) 其中N是数组中存在的总数。 上述实现的重复关系为 T(N)= 2 * T(N / 2)+ O(1).

空间复杂度

O(1) 在这里,除了给定数组之外,我们没有创建任何额外的空间,因此,空间复杂度是O(1),它是恒定的。

使用的算法类型

在这里,我们使用分而治之的方法来解决合并排序。

參考資料