10-归并排序算法

2022-02-25 08:59:23 浏览数 (1)

思想:

分治 归并 通过分治缩减排序规模,然后再将分治后的答案进行归并,逐渐得到原答案。

注意点:
  • 稳定的排序算法
  • 时间复杂度O(nlog2n)
  • 空间复杂度O(n)
  • 非递归实现,自定上下
  • 注意分治和归并中数组中间位置下标的对应关系
  • 应用:逆序对个数的求解
代码:
代码语言:javascript复制
#include <stdio.h>
#include <stdlib.h>
typedef int bool;
#define true 1
#define false 0

void swap(int *a, int* b) {
    int t = *a;
    *a = *b;
    *b = t;
}


void show(int *a, int n) {
    int i = 0;
    for (i = 0; i < n; i  ) {
        printf("%d", a[i]);
        if (i != n - 1) {
            printf(" ");
        }
    }
    printf("n");
}


/*
这里的m很关键
left = [l, m-1] right = [m, r]
*/
void Merge(int *a, int l, int m, int r) {
    int leftSize = m - l;
    int rightSize = r - m   1;
    int* left = (int*)malloc(sizeof(int) * leftSize);
    if (!left) {
        printf("malloc fail!");
        return;
    }
    int *right = (int*)malloc(sizeof(int) * rightSize);
    if (!right) {
        printf("malloc fail!");
        return;
    }
    int i = 0;
    for (i = l; i < m; i  ) {
        left[i - l] = a[i]; 
    }
    for (i = m; i <= r; i  ) {
        right[i - m] = a[i];
    }
    i = 0;
    int j = 0;
    int k = l;
    while (i < leftSize && j < rightSize) {
        if (left[i] <= right[j]) {
            a[k  ] = left[i  ];
        } else {
            a[k  ] = right[j  ];
        }
    }
    while (i < leftSize) {
        a[k  ] = left[i  ];
    }

    while (j < rightSize) {
        a[k  ] = right[j  ];
    }
    free(left);
    left = NULL;
    free(right);
    right = NULL;
}


void MergeSort(int *a, int l, int r) {
    if (l >= r) {
        return;
    }
    int m = (r - l) / 2   l;
    MergeSort(a, l, m);
    MergeSort(a, m   1, r);
    Merge(a, l, m   1, r);
}


int main() {
    int a[] = {3, 1, 2, 4, 7, 0, 5, 8, 6, 9};
    int n = sizeof(a) / sizeof(int);
    show(a, n);
    MergeSort(a, 0, n - 1);
    show(a, n);
    return 0;
}

0 人点赞