DAY3-排序(二)

Merge Sort

原理:利用将两有序数组合并只需要线性时间的特性将数组分割,合并

思考&衍伸:

  1. 合并有序数组的技巧:在有序数组後放一个大数(可以解决长度的问题)
  2. 时间复杂度O(n logn)
  3. 有效排序链表
void merge_sort(vector<int>& arr, int l, int r){
    if(l>=r){
        return;
    }
    int mid = (r+l)/2;
    merge_sort(arr, l, mid);
    merge_sort(arr, mid+1, r);
    
    vector<int> l_arr(arr.begin()+l, arr.begin()+mid+1);
    vector<int> r_arr(arr.begin()+mid+1, arr.begin()+r+1);
    l_arr.insert(l_arr.end(), INT_MAX);
    r_arr.insert(r_arr.end(), INT_MAX);
    int i = 0,j = 0;
    for(int k = l;k<=r; k++){
        if(l_arr[i]<=r_arr[j]){
            arr[k] = l_arr[i];
            i++;
        }
        else{
            arr[k] = r_arr[j];
            j++;
        }
    }
}

不反复宣告子阵列的写法

传入与arr大小相同的split阵列

void merge_sort(vector<int>& arr, vector<int> split, int l, int r){
    if(l>=r){
        return;
    }
    int mid = (r+l)/2;
    merge_sort(arr, split,l, mid);
    merge_sort(arr, split,mid+1, r);
    for(int i = l; i<r+1; ++i){
        split[i] = arr[i];
    }
    int i = l,j = mid+1;
    for(int k = l;k<=r; k++){
        if(i==mid+1){
            arr[k] = split[j++];
        }
        else if(j==r+1){
            arr[k] = split[i++];
        }
        else if(split[j]<split[i]){
            arr[k] = split[j++];
        }
        else{
            arr[k] = split[i++];
        }
    }
}

例题实战

21. Merge Two Sorted Lists
这题虽然不算是Merge Sort...但有用到合并的操作,所以放入例题(等等下一题会用到)
递回比较直观,可读性也高,迭代的细节写在注解

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {

        // 递回法
        // if(l1==NULL)
        //     return l2;
        // if(l2==NULL)
        //     return l1;
        // if(l1->val < l2->val){
        //     l1->next = mergeTwoLists(l1->next, l2);
        //     return l1;
        // }
        // else{
        //     l2->next = mergeTwoLists(l2->next, l1);
        //     return l2;
        // }
        // return l1;

        //迭代法
        ListNode* preHead = new ListNode(-1);
        ListNode* preHead_temp = preHead; // 用於保留root节点
        while(l1!=NULL && l2!=NULL){
            if(l1->val < l2->val){
                preHead->next = l1;
                l1 = l1->next;  
            }
            else{
                preHead->next = l2;
                l2 = l2->next;
            }
            preHead = preHead->next;
        }

        // 最後会剩l1或是l2,将其合并进去
        if(l1!=NULL){
            preHead->next = l1;
        }
        else{
            preHead->next = l2;
        }
        return preHead_temp->next;

    }
};

148. 排序链表
如果有写过上面那一题,就会发现Merge Sort拿来排序链表很适合~~

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* sortList(ListNode* head) {
        if(head==nullptr||head->next==nullptr){
            return head;
        }
        ListNode* first_right_node = cut_from_mid(head);
        ListNode* right = sortList(head);
        ListNode* left = sortList(first_right_node);
        ListNode* res = merge(right, left);
        return res;
    }

    //将List从中间分割成左链和右链,返回第一个右链节点
    ListNode* cut_from_mid(ListNode* head){
        ListNode* slow = head;
        ListNode* fast = head;
        ListNode* slow_f = nullptr; //走在slow後面,用於断开左右链
        while(fast&&fast->next){
            slow_f = slow;
            fast = fast->next->next;
            slow = slow->next;
        }
        slow_f->next = nullptr; //断开左右链
        return slow; //回传右链第一个节点
    }
    //预设左右长度只差1 (分割时保证)
    ListNode* merge(ListNode* left, ListNode* right){
        ListNode* new_head = new ListNode();
        ListNode* curr = new_head;
        while(left&&right){
            if(left->val < right->val){
                curr->next = left;
                left = left->next;
            }
            else{
                curr->next = right;
                right = right->next;
            }
            curr = curr->next;
        }
        curr->next = left?left:right;
        return new_head->next;
    }
};

剑指 Offer 51. 数组中的逆序对
经典的Merge Sort应用,合并两个排序数组时,可以顺便统计逆序对
特别解释一下程序码中更新res的mid-i+1
在tmp[i]>tmp[j]情况下,保证tmp[i]~tmp[mid]都比tmp[j]大,而这些都会形成逆序对,所以逆序对增加mid-i+1!!
有这个理解下,这题只是要实现一下Merge Sort而已

class Solution {
    int res = 0;
public:
    int reversePairs(vector<int>& nums) {
        /*
        思路:
        merge sort合并两个有数组时计算有多少逆序对
        */
        int n = nums.size();
        vector<int> tmp(n);
        merge_sort(0, n-1, nums, tmp);
        return res;
    }
    void merge_sort(int l, int r,vector<int>& nums, vector<int>& tmp){
        if(l>=r){
            return;
        }
        int mid = (l+r)/2; //mid是左数组的尾
        merge_sort(l, mid, nums, tmp);
        merge_sort(mid+1, r, nums, tmp);
        //利用tmp保存两有序数组, tmp[l]~tmp[mid]是左数组, tmp[mid+1]~tmp[r]是右数组
        for(int k = l; k<=r; ++k){
            tmp[k] = nums[k];
        }
        int i = l, j = mid+1;
        for(int k = l; k<=r; ++k){
            if(i>mid){
                nums[k] = tmp[j++];
            }
            else if(j>r){
                nums[k] = tmp[i++];
            }
            else if(tmp[i]<=tmp[j]){
                nums[k] = tmp[i++];
            }
            else{ //tmp[j]<tmp[i] 出现逆序对
                nums[k] = tmp[j++];
                res+=mid-i+1;
            }
        }
    }
};

Merge Sort的分治思路很容易在题目出现,刷过几题之後出现类似的题目会好思考一点(?
/images/emoticon/emoticon22.gif


<<:  Ruby on Rails Find Find_by Where 差别

>>:  Day03-搞懂传址、传值? 电脑如何储存资料?

【第二十八天 - XSS Lab(2)-6】

Q1. XSS Lab(2)-6 题目:https://alf.nu/alert1 Quine 题目...

Android 学习笔记27

继第22篇已经可以绑定fragment跟viewpager那我们就在fragment中加入一些东西吧...

Day 7:AWS是什麽?30天从动漫/影视作品看AWS服务应用 -《PSYCHO-PASS心灵判官》part1

提到健康监控系统,就不可不提鼎鼎大名的《PSYCHO-PASS心灵判官》中的希必拉系统Sibyl S...

day27_ARM 在 Server 领域的发展 (下)

云端托管服务 云端托管服务其实相当於使用硬体供应商准备的 Server 来运行我们准备的服务,他们可...

CMMC 2.0 之前世今生

美国国防部在 2020 年1月底公布新规范 「网路安全成熟度模型认证Cybersecurity Ma...