笔记

将数组一分为二，分别将两个子数组有序，然后再合并两个有序子数组

注意

稳定排序

#include<bits/stdc++.h>

using namespace std;


/**
 * 归并排序
 * */

void merge(int a[], int left, int mid, int right);

void merge_sort(int a[], int left, int right) {
    if(right <= left) {
        return ;
    }

    int mid = left + (right-left)/2;
    merge_sort(a, left, mid);
    merge_sort(a, mid+1, right);
    merge(a, left, mid, right);
}

void merge(int a[], int left, int mid, int right) {
    int temp[right-left+1];
    int k = 0;
    int i = left, j = mid+1;
    while(i <= mid && j <= right) {
        if(a[i] < a[j]) {
            temp[k++] = a[i++];
        }
        else{
            temp[k++] = a[j++];
        }
    }
    while(i <= mid) {
        temp[k++] = a[i++];
    }
    while(j <= right) {
        temp[k++] = a[j++];
    }
    assert(k == right-left+1);
    for(int t = 0; t < k; t++) {
        a[t+left] = temp[t];
    }
}



int main() {
    int a[] = {9, 3, 1, 4, 2, 7, 8, 6, 5};

    int len = sizeof(a)/sizeof(a[0]);

    merge_sort(a, 0, len-1);

    for(int i = 0; i < len; i++) {
        printf("%d%c", a[i], " \n"[i==len-1]);
    }
    return 0;
}

参考链接

菜鸟教程 (opens new window)