原地归并排序

算法思想

有这样的一个问题，要使得两个有序的数组，合并成一个有序的数组。归并排序就是以这样的想法递归地对一个无序的数组进行排序。

先来思考：如何才能能将两个有序的数组，合并成一个有序的数组。

因为两个数组是有序的，所以使用指针指向这两个数组的首元，一一进行比较。

  • 较小的一方放在新数组的前面，并且往后移动指针。
  • 如果，指针越过了数组范围，那么就把另一个数组的所有元素放到新数组的最后面。

算法描述

  • 格外开通一个辅助数组aux[]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

int less_(int a, int b)
{
    if (a < b)
        return 1;
    else
        return 0;
}

void merge(int a[], int lo, int mid, int hi)
{
    int i = lo, j = mid + 1;
    int aux[maxsize];
    for (int k = lo; k <= hi; k++)
        aux[k] = a[k];//辅助数组

    for (int k = lo; k <= hi; k++)
    {
        if (i > mid)
            a[k] = aux[j++];
        else if (j > hi)
            a[k] = aux[i++];
        else if (less_(aux[j], aux[i]))
            a[k] = aux[j++];
        else
            a[k] = aux[i++];
    }
}

int main(int argc, char const *argv[])
{
    int a[] = {1,2,9,   0,2};	//先决条件，左右两边都有序
    int length = sizeof(a) / sizeof(a[0]);
    int lo=0;
    int hi=length-1;
    int mid=(lo+hi)/2;

    merge(a, lo, mid, hi);
    for (int i = 0; i < length; i++)
    {
        cout << a[i] << " ";
    }
    return 0;
}

无需开通额外数组

上一算法中，需要开通额外数组复制数据。下面的算法不是针对一个数组的排序（其实前面的两个是我们自己拆分的，这里是真的两个数组），他能将有序A数组和有序B数组合并，并排序，最终结果放到A（前提A够大）

算法描述

这里稍微修改了一下：

  • 限定A的数组长度na+nb
  • 把大的一方往A最后放，并--1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
int comb(int A[], int &na, int B[], int nb){
    if(na+nb>MAXSIZE)
        return -1;
    int i=na, j=nb;
    while (j>0)
    {
        if(i==0||A[i-1]<B[j-1]){
            A[j+i-1]=B[j-1];
            --j;
        }
        else{
            A[j+i-1]=A[i-1];
            --i;
        }
    }
    na=na+nb;
    return na;
}

int main(int argc, char const *argv[])
{

    int na=3;
    int nb=3;
    // merge(l);
    int a[MAXSIZE]={1,2,8};
    int b[MAXSIZE]={3,4,5};
    comb(a,na,b,nb);
    display(a);
    return 0;
}

Practice

  1. 有两个递增数组A,B。组成将A，B中相同的元素进行从大到小排序的数组C
    • 因为是C从大到小，而A，B递增，所以指针首先指向A，B的最后。
    • 根据归并排序的算法思想，非常简单
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include<iostream>
using namespace std;

int merge(int a[], int na, int b[], int nb, int c[], int &nc){
    int i=na-1;
    int j=nb-1;
    int k=0;
    while (j>=0 && i>=0)
    {
        if(a[i]==b[j]){
            c[k]=a[i];
            k++;
            i--;
            j--;
        }
        else if(a[i]<b[j]){
            j--;
        }
        else{
            i--;
        }
    }
    nc=k;
    return nc;
}

void display(int c[], int n){
    for(int i=0;i<n;i++)
        cout<<c[i]<<" ";
}

int main(int argc, char const *argv[])
{
    int a[4]={1,3,5,6};
    int b[4]={2,3,6,8};
    int c[4];
    int na=4;
    int nb=4;
    int nc=merge(a,4,b,4,c,nc);
    display(c,nc);

    return 0;
}