归并排序和基数排序是什么

归并排序和基数排序都是常见的排序算法。

归并排序是一种分治算法，它将待排序的数组不断地分割成更小的子数组，直到每个子数组只有一个元素。然后，将这些子数组两两合并，直到最终得到一个有序的数组。归并排序的核心思想是将两个有序的子数组合并成一个有序的数组。它的时间复杂度为O(nlogn)，其中n是待排序数组的长度。

基数排序是一种非比较排序算法，它根据元素的位数进行排序。基数排序的核心思想是将待排序的元素按照低位到高位的顺序依次进行排序。具体操作是将元素按照个位数进行排序，然后按照十位数进行排序，以此类推，直到最高位。基数排序可以使用桶排序或计数排序作为辅助算法。它的时间复杂度为O(d*(n+r))，其中d是最大元素的位数，n是待排序数组的长度，r是基数的范围。

相关问题

C语言归并排序与基数排序代码

归并排序代码：

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

void merge(int arr[], int left, int mid, int right)
{
    int len = right - left + 1;
    int *temp = (int*)malloc(sizeof(int)*len);
    int i = left, j = mid + 1, k = 0;

    while (i <= mid && j <= right)
    {
        if (arr[i] < arr[j])
            temp[k++] = arr[i++];
        else
            temp[k++] = arr[j++];
    }

    while (i <= mid)
        temp[k++] = arr[i++];

    while (j <= right)
        temp[k++] = arr[j++];

    for (int m = 0; m < len; m++)
        arr[left + m] = temp[m];

    free(temp);
}

void merge_sort(int arr[], int left, int right)
{
    if (left >= right)
        return;

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

int main()
{
    int arr[] = { 3, 2, 1, 5, 4 };
    int len = sizeof(arr) / sizeof(int);

    merge_sort(arr, 0, len - 1);

    for (int i = 0; i < len; i++)
        printf("%d ", arr[i]);

    return 0;
}

基数排序代码：

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

int get_max(int arr[], int len)
{
    int max = arr[0];
    for (int i = 1; i < len; i++)
    {
        if (arr[i] > max)
            max = arr[i];
    }
    return max;
}

void radix_sort(int arr[], int len)
{
    int max = get_max(arr, len);
    int *count = (int*)malloc(sizeof(int) * (max + 1));
    int *temp = (int*)malloc(sizeof(int) * len);
    int radix = 1;

    while (max / radix > 0)
    {
        for (int i = 0; i < max + 1; i++)
            count[i] = 0;

        for (int i = 0; i < len; i++)
            count[arr[i] / radix % 10]++;

        for (int i = 1; i < max + 1; i++)
            count[i] += count[i - 1];

        for (int i = len - 1; i >= 0; i--)
            temp[--count[arr[i] / radix % 10]] = arr[i];

        for (int i = 0; i < len; i++)
            arr[i] = temp[i];

        radix *= 10;
    }

    free(count);
    free(temp);
}

int main()
{
    int arr[] = { 329, 457, 657, 839, 436, 720, 355 };
    int len = sizeof(arr) / sizeof(int);

    radix_sort(arr, len);

    for (int i = 0; i < len; i++)
        printf("%d ", arr[i]);

    return 0;
}

在插入排序、希尔排序、选择排序、快速排序、堆排序、归并排序和基数排序中，排序是不稳定的有

快速排序、堆排序和基数排序是不稳定的排序算法。其中，快速排序是通过交换元素来进行排序的，可能会改变相同元素的相对位置；堆排序是通过选择最值并交换来进行排序的，也可能会改变相同元素的相对位置；基数排序是通过多轮排序来对元素进行排序的，每轮排序都有可能改变相同元素的相对位置。而插入排序、希尔排序、选择排序和归并排序都是稳定的排序算法。