C语言归排与计排深度理解

什么是排序算法？

排序算法是计算机程序设计中最常见的问题之一。排序算法是一种将输入元素按特定顺序排列的算法。排序算法分为内部排序和外部排序：
- 对于内存（内部）排序，其输入和输出均存储在计算机内存中。
- 对于外存（外部）排序，其输入或输出涉及到显式的输入/输出操作，通常通过磁带、磁盘或因特网进行数据传输和存储。

本篇文档主要介绍内部排序算法中的归排和计排。

什么是归并排序算法？

归并排序是一种基于分治策略的排序算法。归并排序的基本思想是将无序的一组数据分成两个子序列，然后递归地对这两个子序列进行排序，并将排序后的子序列再合并成一个有序的序列。

下面是一个简单的归并排序的示例实现：

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);
    }
}

什么是计数排序算法？

计数排序算法是一种用于整数排序的线性排序算法。计数排序算法的基本思想是对于每一个输入元素x，确定小于x的元素个数。

下面是一个简单的计数排序的示例实现：

void CountSort(int arr[], int n)
{
    int i, j, k;
    int max = arr[0], min = arr[0];
    for (i = 1; i < n; i++) {
        if (arr[i] > max)
            max = arr[i];
        if (arr[i] < min)
            min = arr[i];
    }

    int len = max - min + 1;
    int* cnt = (int*)malloc(sizeof(int) * len);
    memset(cnt, 0, sizeof(int)*len);
    for (i = 0; i < n; i++)
        cnt[arr[i] - min]++;

    k = 0;
    for (i = 0; i < len; i++) {
        for (j = 0; j < cnt[i]; j++) {
            arr[k++] = i + min;
        }
    }
    free(cnt);
}

总结

归并排序算法和计数排序算法都是在内部排序中使用的常见的排序算法。虽然它们的实现方式不同，但各自都有适用的场景。应根据具体情况选择合适的算法以提高排序效率。