数据结构（C语言篇）：（十九）归并排序和非比较排序

// 合并两个有序子数组
// arr: 原始数组
// left: 左子数组起始索引
// mid: 中间索引（左子数组结束索引）
// right: 右子数组结束索引
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 = (int*)malloc(n1 * sizeof(int));
    int *R = (int*)malloc(n2 * sizeof(int));
    
    // 复制数据到临时数组
    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++;
    }
    
    // 释放临时数组内存
    free(L);
    free(R);
}

// 归并排序主函数
// arr: 要排序的数组
// left: 起始索引
// right: 结束索引
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 TestOP()
{
    srand(time(0));
    const int N = 100000;
    int* a1 = (int*)malloc(sizeof(int)*N);
    int* a2 = (int*)malloc(sizeof(int)*N);
    int* a3 = (int*)malloc(sizeof(int)*N);
    int* a4 = (int*)malloc(sizeof(int)*N);
    int* a5 = (int*)malloc(sizeof(int)*N);
    int* a6 = (int*)malloc(sizeof(int)*N);
    int* a7 = (int*)malloc(sizeof(int)*N);
    for (int i = 0; i < N; ++i)
    {
        a1[i] = rand();
        a2[i] = a1[i];
        a3[i] = a1[i];
        a4[i] = a1[i];
        a5[i] = a1[i];
        a6[i] = a1[i];
        a7[i] = a1[i];
    }
    int begin1 = clock();
    InsertSort(a1, N);
    int end1 = clock();

    int begin2 = clock();
    ShellSort(a2, N);
    int end2 = clock();

    int begin3 = clock();
    SelectSort(a3, N);
    int end3 = clock();

    int begin4 = clock();
    HeapSort(a4, N);
    int end4 = clock();

    int begin5 = clock();
    QuickSort(a5, 0, N-1);
    int end5 = clock();

    int begin6 = clock();
    MergeSort(a6, N);
    int end6 = clock();

    int begin7 = clock();
    BubbleSort(a7, N);
    int end7 = clock();

    printf("InsertSort:%d\n", end1 - begin1);
    printf("ShellSort:%d\n", end2 - begin2);
    printf("SelectSort:%d\n", end3 - begin3);
    printf("HeapSort:%d\n", end4 - begin4);
    printf("QuickSort:%d\n", end5 - begin5);
    printf("MergeSort:%d\n", end6 - begin6);
    printf("BubbleSort:%d\n", end7 - begin7);

    free(a1);
    free(a2);
    free(a3);
    free(a4);
    free(a5);
    free(a6);
    free(a7);
}

// 计数排序函数
// arr: 待排序数组
// n: 数组元素个数
// 返回值: 排序后的新数组（需要手动释放内存）
int* countingSort(int arr[], int n) {
    if (n <= 0) return NULL;
    
    // 1. 找出数组中的最大值和最小值
    int min = arr[0];
    int max = arr[0];
    for (int i = 1; i < n; i++) {
        if (arr[i] < min) {
            min = arr[i];
        }
        if (arr[i] > max) {
            max = arr[i];
        }
    }
    
    // 2. 计算数据范围并创建计数数组
    int range = max - min + 1;
    int* count = (int*)calloc(range, sizeof(int));  // 初始化为0
    if (count == NULL) {
        printf("内存分配失败\n");
        return NULL;
    }
    
    // 3. 统计每个元素出现的次数
    for (int i = 0; i < n; i++) {
        count[arr[i] - min]++;  // 映射到计数数组的索引
    }
    
    // 4. 计算前缀和，确定每个元素的结束位置
    for (int i = 1; i < range; i++) {
        count[i] += count[i - 1];
    }
    
    // 5. 构建结果数组（倒序遍历保证稳定性）
    int* result = (int*)malloc(n * sizeof(int));
    if (result == NULL) {
        printf("内存分配失败\n");
        free(count);
        return NULL;
    }
    
    for (int i = n - 1; i >= 0; i--) {
        // 根据计数数组确定当前元素的位置
        int index = count[arr[i] - min] - 1;
        result[index] = arr[i];
        count[arr[i] - min]--;  // 更新计数
    }
    
    // 释放计数数组
    free(count);
    return result;
}