C++深入理解归并排序的用法

什么是归并排序

归并排序是一种经典的分治算法，它将一个大问题分解成小问题来解决。通过不断将两个已排好序的子序列合并成一个更大的已排好序的序列，最终达到整个序列有序的目的。由于采用了分治思想，时间复杂度为 O(NlogN)，是一种比较高效的排序算法。

归并排序的实现

关键思想

归并排序的核心思想是分治。我们将待排序的序列分成两半，分别对两半进行排序，然后将排好序的两半合并成一个有序序列。

实现步骤

1. 递归分解待排序数组

2. 合并两个有序数组

代码实现

以下为归并排序的C++代码实现：

void mergesort(vector<int>& nums, int start, int end){
    if(start >= end) return;
    int mid = start + (end-start)/2;
    mergesort(nums, start, mid);
    mergesort(nums, mid+1, end);
    merge(nums, start, mid, end);
}

void merge(vector<int>& nums, int start, int mid, int end){
    vector<int> tmp(end-start+1);
    int i = start, j = mid+1, k = 0;
    while(i <= mid && j <= end){
        if(nums[i] < nums[j]){
            tmp[k++] = nums[i++];
        }else{
            tmp[k++] = nums[j++];
        }
    }
    while(i <= mid){
        tmp[k++] = nums[i++];
    }
    while(j <= end){
        tmp[k++] = nums[j++];
    }
    for(int i = start; i <= end; i++){
        nums[i] = tmp[i-start];
    }
}

使用归并排序解决问题

归并排序的应用非常广泛，例如：

问题1：求逆序对数量

逆序对指的是在一个序列中，左边的数大于右边的数的数对数量。归并排序可以通过在合并两个有序数组的时候，统计逆序对数量来解决这个问题。

以下为求逆序对数量的C++代码实现：

int count_inversion(vector<int>& nums, int start, int end){
    if(start >= end) return 0;
    int mid = start + (end-start)/2;
    int left = count_inversion(nums, start, mid);
    int right = count_inversion(nums, mid+1, end);
    int cnt = 0, i = start, j = mid+1;
    vector<int> tmp(end-start+1);
    int k = 0;
    while(i <= mid && j <= end){
        if(nums[i] <= nums[j]){
            tmp[k++] = nums[i++];
        }else{
            tmp[k++] = nums[j++];
            cnt += mid-i+1;
        }
    }
    while(i <= mid){
        tmp[k++] = nums[i++];
    }
    while(j <= end){
        tmp[k++] = nums[j++];
    }
    for(int i = start; i <= end; i++){
        nums[i] = tmp[i-start];
    }
    return cnt+left+right;
}

问题2：求逆序对数量

归并排序还可以用来对链表进行排序，特别是当链表很长时，归并排序比快速排序更稳定、效率更高。

以下为链表排序的C++代码实现：

ListNode* mergeSort(ListNode* head){
    if(head == NULL || head->next == NULL){
        return head;
    }
    ListNode* fast = head->next;
    ListNode* slow = head;
    while(fast && fast->next){
        slow = slow->next;
        fast = fast->next->next;
    }
    ListNode* mid = slow->next;
    slow->next = NULL;
    ListNode* left = mergeSort(head);
    ListNode* right = mergeSort(mid);
    return merge(left, right);
}

ListNode* merge(ListNode* l, ListNode* r){
    if(l == NULL) return r;
    if(r == NULL) return l;
    if(l->val < r->val){
        l->next = merge(l->next, r);
        return l;
    }else{
        r->next = merge(l, r->next);
        return r;
    }
}

结语

归并排序是一种非常实用的排序算法，代码实现不难，但理解其原理则需要更深刻的思考。在实际编程时，我们可以借助冒泡和快速排序的思想，来更好地理解归并排序。