对分段有序的数组排序（前、后部分分别递增）

1 题目

设m+n个元素顺序存放在数组A[1…m+n]中，前m个元素递增有序，后n个元素递增有序，试设计一个在时间和空间两方面都尽可能高效的算法，使得整个顺序表递增有序。

2 思路

2.1 思路1（直接插入法）

把数组A看作是两个长度分别为m和n的有序表L1、L2，把L2的每个元素依次插入到L1中的合适位置即可。

• 1，取表L2中第一个元素A[m+1]，暂存为tmp，把tmp插入到L1中合适的位置（L[i]
• 2，重复操作1，把A[m+2]、A[m+3]…A[m+n]依次插入到L1中，直至整个数组有序。

时间复杂度：O(mn)
空间复杂度：O（1）

2.2 思路2（归并）

• 1，把数组A前m个元素和后n个元素视为两个归并段L1、L2，增加一个辅助数组B[1…m+n]存储临时归并的结果。设k1、k2、k3分别指向L1，L2的首位和数组B的下一个结果位置。
• 2，当k1<=m并且k2<=m+n时，执行3，否则执行4:
• • 3，比较两个归并段指针所指元素的大小，若A[k1]
• • 4，若k1>m，则把第二归并段剩余的元素复制到数组B末尾；若k2>m+n,则把第一个归并段剩余的元素复制到数组B，最后把数组B复制到数组A。

时间复杂度：O(m+n)
空间复杂度：O(m+n)

3 实现

3.1 思路1

#include

void solution1(int *A, int m, int n){
    int tmp, j;
    for(int i = m+1; i <= m+n;i++){
        tmp = A[i];//暂存元素，防止后面移动元素时，元素丢失
        for(j = i-1;j > 0 && A[j] > tmp;j--)//当L1中的元素大于tmp时，就是插入tmp的位置
            A[j+1] = A[j];
        A[j+1] = tmp;
    }
}

void print(int* A, int n){
    for(int i = 0;i < n;i++)
    {
        printf("%d ", A[i]);
    }
    printf("\n");
}

int main(){
    int A[] = {0, 1,4,7,2,3,6};
    solution(A, 3, 3);
    print(A, sizeof(A)/sizeof(A[0]));
    return 0;
}
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

3.2 思路2

#include

void solution2(int *A, int m, int n){
    int B[m+n+1];
    int k1 = 1, k2 = m+1, k3 = 1;//三个指针
    while(k1<=m && k2<= m+ n){//归并，把较小的元素复制到B中
        if(A[k1] < A[k2]) B[k3++] = A[k1++];
        else B[k3++] = A[k2++];
    }
    if(k1 > m) //把没有比较完的归并段的剩余元素复制到B中
        while(k2 <= m+n) B[k3++] = A[k2++];
    if(k2 > m+n)
        while(k1 <= m) B[k3++] = A[k1++];
    for(int i = 1;i <= m+n;i++){//把数组B复制到数组A中
        A[i] = B[i];
    }
} 

void print(int* A, int n){
    for(int i = 0;i < n;i++)
    {
        printf("%d ", A[i]);
    }
    printf("\n");
}

int main(){
    int A[] = {0, 1,4,7,2,3,6};
    solution2(A, 3, 3);
    print(A, sizeof(A)/sizeof(A[0]));
    return 0;
}
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