面试题：C语言优化归并排序

优化思路

传统归并排序空间复杂度分析：传统归并排序在合并过程中，需要额外开辟与原数组大小相同的辅助数组来暂存数据，空间复杂度为 $O(n)$。
优化方向：可以采用原地归并的方式，减少额外空间的使用。原地归并的基本思想是通过在原数组上进行局部的合并操作，尽量减少对额外数组的依赖。一种常见的优化方法是利用插入排序在小规模数据上的优势，对于小规模子数组使用插入排序，减少归并时额外空间的分配。另外，还可以尝试使用链表结构来实现归并排序，链表在合并时可以通过调整指针来避免额外数组的使用。

代码示例

#include <stdio.h>

// 插入排序，用于小规模数组
void insertionSort(int arr[], int left, int right) {
    for (int i = left + 1; i <= right; i++) {
        int key = arr[i];
        int j = i - 1;
        while (j >= left && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
}

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

    int L[n1], R[n2];

    for (int i = 0; i < n1; i++)
        L[i] = arr[left + i];
    for (int j = 0; j < n2; j++)
        R[j] = arr[mid + 1 + j];

    int 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 optimizedMergeSort(int arr[], int left, int right, int threshold) {
    if (left < right) {
        if (right - left + 1 <= threshold) {
            insertionSort(arr, left, right);
        } else {
            int mid = left + (right - left) / 2;

            optimizedMergeSort(arr, left, mid, threshold);
            optimizedMergeSort(arr, mid + 1, right, threshold);

            merge(arr, left, mid, right);
        }
    }
}

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

int main() {
    int arr[] = {12, 11, 13, 5, 6, 7};
    int size = sizeof(arr) / sizeof(arr[0]);
    int threshold = 16; // 设定小规模数组的阈值

    printf("Original array: \n");
    printArray(arr, size);

    optimizedMergeSort(arr, 0, size - 1, threshold);

    printf("Sorted array: \n");
    printArray(arr, size);

    return 0;
}

在上述代码中：

insertionSort 函数：实现了插入排序，用于处理小规模子数组。
merge 函数：传统的合并函数，虽然这里仍使用了额外数组，但通过减少合并次数（对于小规模子数组使用插入排序）整体上减少了额外空间的使用。
optimizedMergeSort 函数：优化后的归并排序，当子数组规模小于 threshold 时，使用插入排序，否则进行常规的归并排序。这样在整体上减少了归并操作，从而减少了额外空间的使用。

另一种使用链表实现归并排序减少空间复杂度的思路：

构建链表结构。
在链表上实现归并操作，通过调整链表节点指针完成合并，避免额外数组的使用。

// 链表节点结构
struct ListNode {
    int val;
    struct ListNode *next;
};

// 创建新节点
struct ListNode* createNode(int val) {
    struct ListNode* newNode = (struct ListNode*)malloc(sizeof(struct ListNode));
    newNode->val = val;
    newNode->next = NULL;
    return newNode;
}

// 合并两个有序链表
struct ListNode* mergeLists(struct ListNode* l1, struct ListNode* l2) {
    struct ListNode dummy;
    dummy.next = NULL;
    struct ListNode* tail = &dummy;

    while (l1 != NULL && l2 != NULL) {
        if (l1->val <= l2->val) {
            tail->next = l1;
            l1 = l1->next;
        } else {
            tail->next = l2;
            l2 = l2->next;
        }
        tail = tail->next;
    }

    if (l1 != NULL) {
        tail->next = l1;
    } else {
        tail->next = l2;
    }

    return dummy.next;
}

// 获取链表长度
int getListLength(struct ListNode* head) {
    int length = 0;
    struct ListNode* current = head;
    while (current != NULL) {
        length++;
        current = current->next;
    }
    return length;
}

// 分割链表
struct ListNode* splitList(struct ListNode* head, int length) {
    struct ListNode* current = head;
    for (int i = 1; i < length / 2; i++) {
        current = current->next;
    }
    struct ListNode* secondHalf = current->next;
    current->next = NULL;
    return secondHalf;
}

// 链表归并排序
struct ListNode* mergeSortList(struct ListNode* head) {
    if (head == NULL || head->next == NULL) {
        return head;
    }
    int length = getListLength(head);
    struct ListNode* secondHalf = splitList(head, length);
    head = mergeSortList(head);
    secondHalf = mergeSortList(secondHalf);
    return mergeLists(head, secondHalf);
}

这种链表实现方式，在合并过程中通过调整指针来实现排序，空间复杂度在理想情况下可以达到 $O(\log n)$（递归调用栈的空间），相比传统数组实现的归并排序，在空间使用上有一定优化。

星途面试题库

面试题：C语言优化归并排序

知识考点

面试题答案

优化思路

代码示例