归并排序(C语言)

算法原理

假设序列共有n个元素，将序列每相邻两个数字进行归并操作（merge)，形成floor(n/2)个序列，排序后每个序列包含两个元素，将上述序列再次归并，形成floor(n/4)个序列，每个序列包含四个元素，重复步骤，直到所有元素排序完毕

代码实现

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

void print_arr(int arr[], int len);

void merge_sort(int arr[], int len);

void merge_arr(int left_arr[], int left_arr_len, int right_arr[], int right_arr_len);

void merge(int left_arr[], int left_arr_len, int right_arr[], int right_arr_len);

int main(int argc, const char * argv[]) {
    int arr[10] =  {5, 2, 6, 0, 3, 9, 1, 7, 4, 8};
    print_arr(arr, 10);
    merge_sort(arr, 10);
    print_arr(arr, 10);
    return 0;
}

void merge_sort(int arr[], int len) {
    if (len > 1) {
        // 分割数组
        int *left_arr = arr;
        int left_arr_len = len / 2;
        int *right_arr = arr + left_arr_len;
        int right_arr_len = len - left_arr_len;
        // 对左右数组分别排序
        merge_sort(left_arr, left_arr_len);
        merge_sort(right_arr, right_arr_len);
        // 合并两个数组
        merge(left_arr, left_arr_len, right_arr, right_arr_len);
    }
}

void merge_arr(int left_arr[], int left_arr_len, int right_arr[], int right_arr_len) {
    int *result_arr = (int *)malloc((left_arr_len+right_arr_len)*sizeof(int));
    int left_index = 0, right_index = 0, result_index = 0;
    while (left_index < left_arr_len && right_index < right_arr_len) {
        if (left_arr[left_index] < right_arr[right_index]) {
            result_arr[result_index++] = left_arr[left_index++];
        } else {
            result_arr[result_index++] = right_arr[right_index++];
        }
    }
    while (left_index < left_arr_len) {
        result_arr[result_index++] = left_arr[left_index++];
    }
    while (right_index < right_arr_len) {
        result_arr[result_index++] = right_arr[right_index++];
    }
    for (int i = 0; i < left_arr_len + right_arr_len; i++) {
        left_arr[i] = result_arr[i];
    }
    free(result_arr);
}

void print_arr(int arr[], int len) {
    for (int i = 0; i < len; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}