排序

讲一组有顺序的元素按大小 (只要定义可以返回 true 或 false 的比较关系，非一定数值比较) 重新调整顺序。

归并排序

归并排序是分而治之策略，每次把两个已经排序的数组按大小关系。算法实现采用了递归实现，依次将数组长度 (1,2…n/4,n/2,n) 内的元素排序合并。

算法实现

void merge(long long int* arr, long long int* tmp, int left, int right, int rightEnd) {
    int i, leftEnd, num, tmpPos;
    leftEnd = right - 1;
    tmpPos = left;
    num = rightEnd - left + 1;

    while(left <= leftEnd && right <= rightEnd) {if (arr[left] <= arr[right]) {tmp[tmpPos++] = arr[left++]; 
        } else {tmp[tmpPos++] = arr[right++];
        }
    }

    while(left <= leftEnd) {tmp[tmpPos++] = arr[left++];
    }

    while(right <= rightEnd) {tmp[tmpPos++] = arr[right++];
    }

    for (i = 0; i < num; i++, rightEnd--) {arr[rightEnd] = tmp[rightEnd];
    }
}

void mSort(long long int* arr, long long int* tmp, int left, int right, int len) {
    int center;
    int i;

    if (left < right) {center = (left + right) / 2;
        mSort(arr, tmp, left, center, len);
        mSort(arr, tmp, center + 1, right, len);
        merge(arr, tmp, left, center + 1, right);
        printf("合并参数：%d %d 结果：", left, right);
        for (i = 0; i < len; i++) {printf("%lld", arr[i]);
        }
        printf("\n");
    }
}

long long int* elrSortMerge(long long int* arr, int len) {
    long long int* tmp;
    
    tmp = malloc(len * sizeof(long long int));
    if (tmp) {mSort(arr, tmp, 0, len - 1, len);
        free(tmp);
    } else {printf("no space for sort merge\n");
    }
    
    return arr;
}

调试调用

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

int main(int argc, char **argv){
    int i;
    long long int arr[] = {6, 2, 4, 1, 3, 5, 0, 8, 9, -1, 7};
    elrSortMerge(arr, 11);
    printf("%d\n", (int)(sizeof(arr) / sizeof(long long int)));
    for (i = 0; i < 11; i++) {printf("%lld", arr[i]);
    }
    printf("\n");
    return 0;
}

输出

合并参数：0 1 结果：2 6 4 1 3 5 0 8 9 -1 7 
合并参数：0 2 结果：2 4 6 1 3 5 0 8 9 -1 7 
合并参数：3 4 结果：2 4 6 1 3 5 0 8 9 -1 7 
合并参数：3 5 结果：2 4 6 1 3 5 0 8 9 -1 7 
合并参数：0 5 结果：1 2 3 4 5 6 0 8 9 -1 7 
合并参数：6 7 结果：1 2 3 4 5 6 0 8 9 -1 7 
合并参数：6 8 结果：1 2 3 4 5 6 0 8 9 -1 7 
合并参数：9 10 结果：1 2 3 4 5 6 0 8 9 -1 7 
合并参数：6 10 结果：1 2 3 4 5 6 -1 0 7 8 9 
合并参数：0 10 结果：-1 0 1 2 3 4 5 6 7 8 9