【数据结构】归并排序

算法描述

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

举例

先拆分成一个一个数字，拆分完成后，按照原拆分路线进行有序合并。

代码实现

#include

using namespace std;

int q[100001];


void sort(int q[], int start, int mid, int end){
    int * res = new int[end - start +1];
    int l = start;
    int r = mid +1;
    int j =0;
    while(l<=mid && r<=end){
        if(q[r] < q[l]){
            res[j] = q[r];
            //cout<
            r++;
        }
        else{
            res[j] = q[l];
            //cout<
            l++;
        }
        j++;
    }
    
    while(l<=mid){
        res[j] = q[l];
        l++;
        j++;
    }
    
    while(r<=end){
        res[j] = q[r];
        r++;
        j++;
    }
    //cout<<"分段后合并的子序列"<
    for(j =0 ; j<end - start +1; j++){
        
        //cout<
        q[start + j] = res[j]; 
    }
    //cout<
    
}

void merge(int q[], int start, int end){
    if(start>=end){
        return;
    }
    int mid = (end + start)>>1;
    merge(q, start, mid);
    merge(q, mid+1, end);
    //cout<<"合并前:";
    //cout<
    sort(q, start, mid, end);
    
}

void mergesort(int q[], int n){
    merge(q, 0, n-1);
    
}


int main(){
    int n;
    cin>>n;
    int i=0;
    for(i=0; i<n; i++){
        cin>>q[i];
    }
    
    mergesort(q, n);
    
    
    for(i=0; i<n; i++){
        cout<<q[i]<<" ";
    }
    
    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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83