算法-归并排序

归并

分治

1. 确定分界点， 中心点
2. 递归左边、右边
3. 归并——合二为一（重难点）

特点

1. 稳定的
2. 时间复杂度：nlog2^n妥妥的

代码语言：javascript复制

#include<iostream>

using namespace std;

const int N = 1e6   10;

int n;
//temp辅助数组存排序结果
int q[N], temp[N];

void merge_sort(int q[], int l, int r){
    if(l >= r) return;
    
    //分界点(l r)/2
    int mid = l   r >> 1; 
    
    //递归
    merge_sort(q, l, mid), merge_sort(q, mid   1, r);
    
    //k已排序个数，i左边起点，j右边起点
    int k = 0, i = l, j = mid   1; 
    while(i <= mid && j <= r)
        if(q[i] <= q[j]) temp[k   ] = q[i   ];
        else temp[k   ] = q[j   ];
    //把未循环完的加到末尾
    while(i <= mid) temp[k   ] = q[i   ];
    while(j <= r) temp[k   ] = q[j   ];
    
    //从排好序的数组中取回
    for(i = l, j = 0; i <= r; i   ,j   ) q[i] = temp[j];
}

int main(){
    scanf("%d", &n);
    for(int i = 0; i < n; i  ) scanf("%d", &q[i]);
    
    merge_sort(q, 0, n - 1);
    
    for(int i = 0; i < n; i  ) printf("%d ", q[i]); 
    
    return 0;
}

递归

0 人点赞