题解 | #排序#

#include <stdio.h>
#include <stdlib.h>

#define Nmax 100

void merge(int numList[], int first, int mid, int last) {

    int i, j;

    //每次需要排序的divided数组大小都不一样
    //进行动态分配临时数组
    int* tmp = (int*)malloc((last - first + 1) * sizeof(int));

    int L_low = first;
    int L_high = mid;
    int R_low = mid + 1;
    int R_high = last;

    //1.compare与copy,L R 比较完后移，排序结果先进tmp数组

    for (i = 0; L_low <= L_high && R_low <= R_high; i++) {
        if (numList[L_low] < numList[R_low]) {
            tmp[i] = numList[L_low];
            L_low++;
        } else {
            tmp[i] = numList[R_low];
            R_low++;
        }
    }

    //2.L left
    if (L_low <= L_high) {
        for (j = L_low; j <= L_high; j++) {
            tmp[i] = numList[j];
            i++;
        }
    }
    //3.R left
    if (R_low <= R_high) {
        for (j = R_low; j <= R_high; j++) {
            tmp[i] = numList[j];
            i++;
        }
    }


    //4.copy 回numList\
    //注意递归，所以first+i
    for (i = 0; i < last - first + 1; i++) {
        numList[first + i] = tmp[i];
    }
    free(tmp);//


}

void merge_sort(int numList[], int first, int last) {

    int mid;

    if (first < last) {
        mid = (first + last) / 2;
        //对Left进行递归分割
        merge_sort(numList, first, mid);
        //对Right进行递归分割
        merge_sort(numList, mid + 1, last);
        merge(numList, first, mid, last);

    }


}





int main() {
    int N, i;
    int numList[Nmax];

    //1.input
    scanf("%d", &N);
    for (i = 0; i < N; i++) {
        scanf("%d", &numList[i]);

    }
    //2.func
    merge_sort(numList, 0, N - 1);


    //3.output
    for (i = 0; i < N; i++) {
        printf("%d ", numList[i]);
    }



}