Skip to content

Latest commit

 

History

History
324 lines (272 loc) · 8.42 KB

归并排序.md

File metadata and controls

324 lines (272 loc) · 8.42 KB
Raw

归并排序时间复杂度分析

归并排序时间复杂度是 $O(nlogn)$
每次将 $n$ 个数划分成两个子区间，当划分到 $logn$ 层的时候，子区间长度就为 $1$
在第 $logn$ 层时，一共有 $n$ 个子区间，将 $n$ 个子区间合并，每个数都会被遍历一次，这一层的时间复杂度为 $O(n)$
在每一层，合并两个区间时，$n$ 个数都会被遍历一次，所以每一层的时间复杂度都是 $O(n)$
总时间复杂度为 $O(nlogn)$

归并排序步骤

  1. 将中点作为分界点
  2. 递归排序左右两部分
  3. 合并两部分

归并排序模板

void merge_sort(int q[], int l, int r){
    if (l >= r) return;
    
    int mid = l + r >> 1;
    merge_sort(q, l, mid), merge_sort(q, mid + 1, r);
    
    int k = 0;
    int i = l, j = mid + 1;
    while (i <= mid && j <= r){
        if (q[i] <= q[j]) tmp[k ++] = q[i ++];
        else tmp[k ++] = q[j ++];
    }
    while (i <= mid) tmp[k ++] = q[i ++];
    while (j <= r) tmp[k ++] = q[j ++];
    
    k = 0;
    while (l <= r) q[l ++] = tmp[k ++];
    
}

归并排序题型

Acwing.787 归并排序

给定你一个长度为 $n$ 的整数数列。

请你使用归并排序对这个数列按照从小到大进行排序。

并将排好序的数列按顺序输出。

输入格式
输入共两行，第一行包含整数 $n$

第二行包含 $n$ 个整数（所有整数均在 $1∼10^9$ 范围内），表示整个数列

输出格式
输出共一行，包含 $n$ 个整数，表示排好序的数列。

数据范围
$1≤n≤10^5$

输入样例：

5
3 1 2 4 5

输出样例：

1 2 3 4 5
  • 解题代码
#include <iostream>

using namespace std;

const int N = 1e5 + 10;

int n;
int q[N], tmp[N];

void merge_sort(int q[], int l, int r){
    if (l >= r) return;
    
    int mid = l + r >> 1;
    merge_sort(q, l, mid), merge_sort(q, mid + 1, r);
    
    int k = 0;
    int i = l, j = mid + 1;
    while (i <= mid && j <= r){
        if (q[i] <= q[j]) tmp[k ++] = q[i ++];
        else tmp[k ++] = q[j ++];
    }
    while (i <= mid) tmp[k ++] = q[i ++];
    while (j <= r) tmp[k ++] = q[j ++];
    
    k = 0;
    while (l <= r) q[l ++] = tmp[k ++];
}

int main(){
    cin >> n;
    
    for (int i = 0; i < n; i ++) cin >> q[i];
    
    merge_sort(q, 0, n - 1);
    
    for (int i = 0; i < n; i ++) 
        cout << q[i] << ' ';
    return 0;
}

Acwing.788 逆序对的数量

给定一个长度为 $n$ 的整数数列，请你计算数列中的逆序对的数量。

逆序对的定义如下：对于数列的第 $i$ 个和第 $j$ 个元素，如果满足 $i&lt;j$ 且 $a[i]&gt;a[j]$，则其为一个逆序对；否则不是。

输入格式
第一行包含整数 $n$，表示数列的长度。

第二行包含 $n$ 个整数，表示整个数列。

输出格式
输出一个整数，表示逆序对的个数。

数据范围
$1≤n≤100000$
数列中的元素的取值范围 $[1,109]$。

输入样例：

6
2 3 4 5 6 1

输出样例：

5
  • 解题思路：
    将数组分成 $[L, mid]$ 和 $[mid + 1, R]$ 两部分之后，$i$ 是 $[L, mid]$ 这一段的下标，$j$ 是 $[mid + 1, R]$ 这一段的下标，$i<j$
    如果 $q[i]&gt;q[j]$ 说明 $q[i] q[i + 1] ... q[mid - 1] q[mid]$ 都大于 $q[j]$，逆序对的数量为 $mid - i + 1$
  • 解题代码
#include <iostream>

using namespace std;

typedef long long LL;

const int N = 1e5 + 10;

int n;
int q[N], tmp[N];
LL res = 0;

void merge_sort(int q[], int l, int r){
    if (l >= r) return;
    
    int mid = l + r >> 1;
    merge_sort(q, l, mid), merge_sort(q, mid + 1, r);
    
    int k = 0;
    int i = l, j = mid + 1;
    while (i <= mid && j <= r){
        if (q[i] <= q[j]) tmp[k ++] = q[i ++];
        else {
            tmp[k ++] = q[j ++];
            res += mid - i + 1;
        }
    }
    while(i <= mid) tmp[k ++] = q[i ++];
    while(j <= r) tmp[k ++] = q[j ++];
    
    k = 0;
    while (l <= r) q[l ++] = tmp[k ++];
}

int main(){
    cin >> n;
    
    for (int i = 0; i < n; i ++) cin >> q[i];
    
    merge_sort(q, 0, n - 1);
    
    cout << res << endl;
    return 0;
}

剑指offer 51.数组中的逆序对

class Solution {
public:
    int res = 0;
    int reversePairs(vector<int>& nums) {
        if (nums.empty()) return 0;
        vector<int> tmp(nums.size());
        merge_sort(nums, tmp, 0, nums.size() - 1);
        return res;
    }

    void merge_sort(vector<int>& nums, vector<int>& tmp, int l, int r){
        if (l >= r) return;

        int mid = (l + r) >> 1;
        merge_sort(nums, tmp, l, mid), merge_sort(nums, tmp, mid + 1, r);
        
        int k = 0;
        int i = l, j = mid + 1;
        while (i <= mid && j <= r){
            if (nums[i] <= nums[j]) tmp[k ++] = nums[i ++];
            else {
                tmp[k ++] = nums[j ++];
                res += mid - i + 1;
            }
        }

        while (i <= mid) tmp[k ++] = nums[i ++];
        while (j <= r) tmp[k ++] = nums[j ++];

        k = 0;
        while (l <= r) nums[l ++] = tmp[k ++];
    }
};

leetcode.21 合并两个有序链表

  • 链接https://leetcode.cn/problems/merge-two-sorted-lists/
  • 解题方法：归并排序
    维护一个当前节点指针
    如果 list1 的值小于 list2，指针指向 list1 并更新当前节点指针和 list1 的指针
    如果 list2 的值小于 list1，指针指向 list2 并更新当前节点指针和 list2 的指针
    如果两个链表长度不同，当一个链表遍历完成，另一个链表没有遍历完成，当前节点指针指向没有遍历完成的链表
  • leetcode解题代码
/**
 * 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* list1, ListNode* list2) {
        auto dummy = new ListNode(-1);
        auto cur = dummy;
        while (list1 && list2){
            if (list1->val < list2->val){
                cur = cur->next = list1;
                list1 = list1->next;
            }
            else{
                cur = cur->next = list2;
                list2 = list2->next;
            }
        }
        if (list1) cur->next = list1;
        if (list2) cur->next = list2;
        return dummy->next;
    }
};

leetcode.148 排序链表

/**
 * 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 || !head->next) return head;

        auto dummy = new ListNode(-1);
        auto f = head, s = head;
        while (f && f->next && f->next->next){
            s = s->next;
            f = f->next->next;
        }

        f = s->next;
        s->next = nullptr;
        
        auto head1 = sortList(head);
        auto head2 = sortList(f);

        auto p = dummy;
        while (head1 && head2){
            if (head1->val < head2->val){
                p->next = head1;
                p = p->next;
                head1 = head1->next;
            }
            else {
                p->next = head2;
                p = p->next;
                head2 = head2->next;
            }
        }
        if (head1) p->next = head1;
        if (head2) p->next = head2;
        return dummy->next;
    }
};