C语言归排与计排是什么

在计算机科学中，排序算法是解决数据排序问题的重要工具。排序算法的目标是将一组数据按照特定的顺序（如升序或降序）进行排列。C语言作为一种广泛使用的编程语言，提供了多种实现排序算法的方式。本文将详细介绍C语言中的归并排序（归排）和计数排序（计排），包括它们的原理、实现方法、优缺点以及应用场景。

1. 归并排序（归排）

1.1 归并排序的基本概念

归并排序（Merge Sort）是一种基于分治法（Divide and Conquer）的排序算法。它的基本思想是将待排序的数组分成两个子数组，分别对这两个子数组进行排序，然后将排好序的子数组合并成一个有序的数组。

1.2 归并排序的步骤

归并排序的主要步骤如下：

1. 分解：将待排序的数组从中间分成两个子数组，直到每个子数组只包含一个元素。
2. 排序：递归地对每个子数组进行排序。
3. 合并：将两个已排序的子数组合并成一个有序的数组。

1.3 归并排序的C语言实现

以下是归并排序的C语言实现代码：

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

// 合并两个有序数组
void merge(int arr[], int left, int mid, int right) {
    int i, j, k;
    int n1 = mid - left + 1;
    int n2 = right - mid;

    // 创建临时数组
    int L[n1], R[n2];

    // 拷贝数据到临时数组
    for (i = 0; i < n1; i++)
        L[i] = arr[left + i];
    for (j = 0; j < n2; j++)
        R[j] = arr[mid + 1 + j];

    // 合并临时数组到原数组
    i = 0;
    j = 0;
    k = left;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    // 拷贝剩余元素
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }

    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}

// 归并排序
void mergeSort(int arr[], int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;

        // 递归排序左半部分
        mergeSort(arr, left, mid);
        // 递归排序右半部分
        mergeSort(arr, mid + 1, right);

        // 合并已排序的部分
        merge(arr, left, mid, right);
    }
}

// 打印数组
void printArray(int arr[], int size) {
    int i;
    for (i = 0; i < size; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

int main() {
    int arr[] = {12, 11, 13, 5, 6, 7};
    int arr_size = sizeof(arr) / sizeof(arr[0]);

    printf("Given array is \n");
    printArray(arr, arr_size);

    mergeSort(arr, 0, arr_size - 1);

    printf("\nSorted array is \n");
    printArray(arr, arr_size);
    return 0;
}

1.4 归并排序的优缺点

优点： - 稳定性：归并排序是一种稳定的排序算法，即相同元素的相对顺序在排序后不会改变。 - 时间复杂度：归并排序的时间复杂度为O(n log n)，在最坏、平均和最好情况下都是如此，适用于大规模数据的排序。 - 适用性：归并排序适用于链表等数据结构，因为它不需要随机访问元素。

缺点： - 空间复杂度：归并排序需要额外的空间来存储临时数组，空间复杂度为O(n)。 - 递归调用：归并排序使用递归实现，递归调用可能会导致栈溢出问题，尤其是在数据量非常大的情况下。

1.5 归并排序的应用场景

归并排序适用于以下场景： - 需要稳定排序的场合。 - 数据量较大且内存空间充足的情况下。 - 需要对链表等数据结构进行排序时。

2. 计数排序（计排）

2.1 计数排序的基本概念

计数排序（Counting Sort）是一种非比较排序算法，适用于整数排序。它的基本思想是通过统计每个元素出现的次数，然后根据统计结果将元素放回原数组的正确位置。

2.2 计数排序的步骤

计数排序的主要步骤如下：

1. 统计频率：统计数组中每个元素出现的次数，并存储在计数数组中。
2. 计算前缀和：将计数数组中的元素累加，得到每个元素在排序后数组中的最终位置。
3. 放置元素：根据计数数组中的信息，将元素放置到排序后数组的正确位置。
4. 输出结果：将排序后的数组输出。

2.3 计数排序的C语言实现

以下是计数排序的C语言实现代码：

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

// 计数排序
void countingSort(int arr[], int n) {
    int max = arr[0];
    for (int i = 1; i < n; i++) {
        if (arr[i] > max) {
            max = arr[i];
        }
    }

    int *count = (int *)calloc(max + 1, sizeof(int));

    // 统计每个元素的出现次数
    for (int i = 0; i < n; i++) {
        count[arr[i]]++;
    }

    // 计算前缀和
    for (int i = 1; i <= max; i++) {
        count[i] += count[i - 1];
    }

    int *output = (int *)malloc(n * sizeof(int));

    // 放置元素到正确位置
    for (int i = n - 1; i >= 0; i--) {
        output[count[arr[i]] - 1] = arr[i];
        count[arr[i]]--;
    }

    // 将排序后的数组拷贝回原数组
    for (int i = 0; i < n; i++) {
        arr[i] = output[i];
    }

    free(count);
    free(output);
}

// 打印数组
void printArray(int arr[], int size) {
    int i;
    for (i = 0; i < size; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

int main() {
    int arr[] = {4, 2, 2, 8, 3, 3, 1};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("Given array is \n");
    printArray(arr, n);

    countingSort(arr, n);

    printf("\nSorted array is \n");
    printArray(arr, n);
    return 0;
}

2.4 计数排序的优缺点

优点： - 时间复杂度：计数排序的时间复杂度为O(n + k)，其中k是数据的范围。当k较小且n较大时，计数排序的效率非常高。 - 稳定性：计数排序是一种稳定的排序算法，即相同元素的相对顺序在排序后不会改变。

缺点： - 空间复杂度：计数排序需要额外的空间来存储计数数组和输出数组，空间复杂度为O(n + k)。 - 适用范围：计数排序仅适用于整数排序，且数据的范围k不能过大，否则会占用大量内存。

2.5 计数排序的应用场景

计数排序适用于以下场景： - 数据范围k较小且数据量n较大的情况下。 - 需要稳定排序的场合。 - 数据为整数且范围已知的情况下。

3. 归并排序与计数排序的比较

3.1 时间复杂度

• 归并排序：时间复杂度为O(n log n)，适用于大规模数据的排序。
• 计数排序：时间复杂度为O(n + k)，适用于数据范围k较小且数据量n较大的情况。

3.2 空间复杂度

• 归并排序：空间复杂度为O(n)，需要额外的空间来存储临时数组。
• 计数排序：空间复杂度为O(n + k)，需要额外的空间来存储计数数组和输出数组。

3.3 稳定性

• 归并排序：稳定的排序算法。
• 计数排序：稳定的排序算法。

3.4 适用范围

• 归并排序：适用于大规模数据的排序，尤其是链表等数据结构。
• 计数排序：适用于整数排序，且数据范围k较小的情况。

4. 总结

归并排序和计数排序是两种常见的排序算法，各有其优缺点和适用场景。归并排序适用于大规模数据的排序，且具有稳定的时间复杂度；而计数排序在数据范围较小的情况下具有较高的效率，但仅适用于整数排序。在实际应用中，应根据具体需求选择合适的排序算法。

通过本文的介绍，读者可以更好地理解归并排序和计数排序的原理、实现方法以及它们的优缺点，从而在实际编程中灵活运用这些排序算法。