归并排序针对性刷题

89 阅读 0 评论 59 点赞

我是靠谱客的博主笨笨夏天，这篇文章主要介绍归并排序针对性刷题，现在分享给大家，希望可以做个参考。

之前对归并排序，只是方法了解，代码不是很熟悉，觉得麻烦。

今天先看视频理解了代码的实现然后自己在codeblocks上打了一遍。

归并排序_哔哩哔哩_bilibili这段视频主要介绍归并排序的算法过程和代码的编写。, 视频播放量 70287、弹幕量 516、点赞数 1337、投硬币枚数 1097、收藏人数 1394、转发人数 237, 视频作者正月点灯笼, 作者简介海外留学党一名，目前在新南威尔士大学读博，大家也可以认为我是无业游民。平时爱好讲讲课，录点教学视频。，相关视频：堆排序(heapsort)，【排序算法精华2】归并排序，分治算法之归并排序，【排序算法】八种排序算法可视化过程，MergeSort-归并排序时间复杂度理解，十分钟学会写归并排序，【搬运】50多种排序算法的可视化，巧用公式法快速求解时间复杂度，排序算法详解（六）归并排序，归并排序 vs 快速排序【代码巴士】https://www.bilibili.com/video/BV1Ax411U7Xx?share_source=copy_web

codeblocks版本：

复制代码

#include<bits/stdc++.h>
using namespace std;

void Merge(int arr[],int L,int M,int R)
{
    int LEFT_SIZE = M-L;
    int RIGHT_SIZE = R-M+1;
    int left[LEFT_SIZE];
    int right[RIGHT_SIZE];
    int i,j,k;

for(int i=L; i<M; i++)left[i-L]=arr[i];
    for(int i=M; i<=R; i++)right[i-M]=arr[i];
    i=0,j=0, k=L;
    while(i<LEFT_SIZE && j<RIGHT_SIZE)
    {
        if(left[i]<right[j])
        {
            arr[k]=left[i];
            k++;
            i++;
        }
        else
        {
            arr[k]=right[j];
            k++;
            j++;
        }
    }
    while(i<LEFT_SIZE)
    {
        arr[k]=left[i];
        i++;
        k++;
    }
    while(j<RIGHT_SIZE)
    {
        arr[k]=right[j];
        j++;
        k++;
    }
}

void mergeSort(int arr[],int L,int R)
{
    if(R == L)return;
    else
    {
        int M=(L+R)/2;
        mergeSort(arr,L,M);
        mergeSort(arr,M+1,R);
        Merge(arr,L,M+1,R);
    }
}

int main()
{
    int arr[]= {3,6,2,5,1,7,9,4};
    int L=0,R=7;
    mergeSort(arr,L,R);
    for(int i=0; i<R; i++)
        cout<<arr[i]<<endl;
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include<bits/stdc++.h>
using namespace std;

void Merge(int arr[],int L,int M,int R)
{
    int LEFT_SIZE = M-L;
    int RIGHT_SIZE = R-M+1;
    int left[LEFT_SIZE];
    int right[RIGHT_SIZE];
    int i,j,k;

    for(int i=L; i<M; i++)left[i-L]=arr[i];
    for(int i=M; i<=R; i++)right[i-M]=arr[i];
    i=0,j=0, k=L;
    while(i<LEFT_SIZE && j<RIGHT_SIZE)
    {
        if(left[i]<right[j])
        {
            arr[k]=left[i];
            k++;
            i++;
        }
        else
        {
            arr[k]=right[j];
            k++;
            j++;
        }
    }
    while(i<LEFT_SIZE)
    {
        arr[k]=left[i];
        i++;
        k++;
    }
    while(j<RIGHT_SIZE)
    {
        arr[k]=right[j];
        j++;
        k++;
    }
}

void mergeSort(int arr[],int L,int R)
{
    if(R == L)return;
    else
    {
        int M=(L+R)/2;
        mergeSort(arr,L,M);
        mergeSort(arr,M+1,R);
        Merge(arr,L,M+1,R);
    }
}

int main()
{
    int arr[]= {3,6,2,5,1,7,9,4};
    int L=0,R=7;
    mergeSort(arr,L,R);
    for(int i=0; i<R; i++)
        cout<<arr[i]<<endl;
    return 0;
}

视频讲的很好，我不过多赘述。

然后在力扣上做了这道手撕题，不知道为什么，题目明明是手撕归并排序，手写完效果好像不太理想，可能交题的人里面直接sort的人太多了！！

但是这题，点进去之后标题又变成了排序数组（莫名其妙..）

直接上那边的笔记吧，其实和codeblocks上写的差不多，也是C++，

就是从int【】转变为 vector<int>

源代码：

复制代码

class Solution {
public:

void Merge(vector<int> &arr,int L,int M,int R){
        int LEFT_SIZE=M-L;
        int RIGHT_SIZE=R-M+1;
        int left[LEFT_SIZE];
        int right[RIGHT_SIZE];
        int i,j,k;

//填充左边数组
        for(int i=L;i<M;i++)left[i-L]=arr[i];
        //填充右边数组 
        for(int i=M;i<=R;i++)right[i-M]=arr[i];
		//把两个数组排序放到arr里去
        i=0,j=0,k=L;
        while(i<LEFT_SIZE && j<RIGHT_SIZE){
            if(left[i]<right[j]){
                arr[k]=left[i];
                i++;
                k++;
            }else{
                arr[k]=right[j];
                j++;
                k++;
            }
        }
        while(i<LEFT_SIZE){
            arr[k]=left[i];
            k++;
            i++;
        }
        while(j<RIGHT_SIZE){
            arr[k]=right[j];
            k++;
            j++;
        }
    }
    void mergeSort(vector<int> &arr,int L,int R){
        if(L==R)return;
        else{
            int M=(L+R)/2;//一刀切
            mergeSort(arr,L,M);//递归，不断分组归并
            mergeSort(arr,M+1,R);
            Merge(arr,L,M+1,R);
        }
    }

vector<int> sortArray(vector<int>& nums) {
        int R=nums.size()-1;
        int L=0;
        mergeSort(nums,L,R);
        return nums;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
class Solution {
public:

    void Merge(vector<int> &arr,int L,int M,int R){
        int LEFT_SIZE=M-L;
        int RIGHT_SIZE=R-M+1;
        int left[LEFT_SIZE];
        int right[RIGHT_SIZE];
        int i,j,k;

    	//填充左边数组
        for(int i=L;i<M;i++)left[i-L]=arr[i];
        //填充右边数组 
        for(int i=M;i<=R;i++)right[i-M]=arr[i];
		//把两个数组排序放到arr里去
        i=0,j=0,k=L;
        while(i<LEFT_SIZE && j<RIGHT_SIZE){
            if(left[i]<right[j]){
                arr[k]=left[i];
                i++;
                k++;
            }else{
                arr[k]=right[j];
                j++;
                k++;
            }
        }
        while(i<LEFT_SIZE){
            arr[k]=left[i];
            k++;
            i++;
        }
        while(j<RIGHT_SIZE){
            arr[k]=right[j];
            k++;
            j++;
        }
    }
    void mergeSort(vector<int> &arr,int L,int R){
        if(L==R)return;
        else{
            int M=(L+R)/2;//一刀切
            mergeSort(arr,L,M);//递归，不断分组归并
            mergeSort(arr,M+1,R);
            Merge(arr,L,M+1,R);
        }
    }

    vector<int> sortArray(vector<int>& nums) {
        int R=nums.size()-1;
        int L=0;
        mergeSort(nums,L,R);
        return nums;
    }
};

然后呢，复习归并排序的主要原因是今天第一是碰到这道题，看了下评论区，大体是要用到归并排序的，但是我不太熟悉，所以回来看看。

题面：

ps：对了，之前做关于链表的题，也经常会遇到要先设置一个dummy结点，然后，令dummy-》next=head。我通常把这玩意取名为preAns，因为结果的返回是这样子写的：return preAns-》next；

当时只知道这个是加个空表头，防止空指针问题的。然后今天在评论区看到了更好理解的解释：

dummy：哑链表头。临时创建的一个链表头，把边界情况和普通情况做统一处理。

这道题同样也用到了dummy。

搞了好久，归并加个链表，确实好麻烦啊！！

复制代码

class Solution {
public:

//断连！将链表切掉前 n 个结点，并返回后半部分的链表头
    ListNode *cut(ListNode* head, int n) {
        ListNode *p = head;
        n=n-1;//因为移动到第n个位置只需要在头结点的位置的基础上走n-1步
        while (p && n--) 
            p = p->next;
        if (p==NULL) return NULL;
        ListNode* behind = p->next;
        p->next = NULL;//p指向的地址为空成为了野指针，*behind=p->next之后，必须加上 p->next=NULL;
        return behind;
    }

//链表版本的双路归并
     ListNode* merge(ListNode* l1, ListNode* l2) {
        ListNode *dummy = new ListNode(-1);
        ListNode* p = dummy;
        while (l1 && l2) {
            if (l1->val < l2->val) {
                p->next = l1;
                p = l1;
                l1 = l1->next;       
            } else {
                p->next = l2;
                p = l2;
                l2 = l2->next;
            }
        }
        if(l1)p->next=l1;
        if(l2) p->next=l2;

return dummy->next;
    }

ListNode* sortList(ListNode* head) {
        if(head==NULL)return{};//判空
        ListNode *dummy = new ListNode(-1);
        dummy->next = head;
        ListNode *p=dummy->next;
        int len=0;
        while(p!=NULL){
            len++;
            p=p->next;
        }//计算出链表的结点个数len
                               //下面这里size的循环运算通过位运算除2，可以大大提升速度（否则会T的）
        for(int size=1;size<len;size<<=1){
            ListNode *cur=dummy->next;
            ListNode *tail=dummy;
            while(cur!=NULL){
                ListNode *left=cur;
                ListNode *right=cut(left,size);
                cur=cut(right,size);

tail->next=merge(left,right);
                while(tail->next!=NULL)
                    tail=tail->next;
            }
        }
        return dummy->next;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
class Solution {
public:

    //断连！将链表切掉前 n 个结点，并返回后半部分的链表头
    ListNode *cut(ListNode* head, int n) {
        ListNode *p = head;
        n=n-1;//因为移动到第n个位置只需要在头结点的位置的基础上走n-1步
        while (p && n--) 
            p = p->next;
        if (p==NULL) return NULL;
        ListNode* behind = p->next;
        p->next = NULL;//p指向的地址为空成为了野指针，*behind=p->next之后，必须加上 p->next=NULL;
        return behind;
    }

     //链表版本的双路归并
     ListNode* merge(ListNode* l1, ListNode* l2) {
        ListNode *dummy = new ListNode(-1);
        ListNode* p = dummy;
        while (l1 && l2) {
            if (l1->val < l2->val) {
                p->next = l1;
                p = l1;
                l1 = l1->next;       
            } else {
                p->next = l2;
                p = l2;
                l2 = l2->next;
            }
        }
        if(l1)p->next=l1;
        if(l2) p->next=l2;

        return dummy->next;
    }


    ListNode* sortList(ListNode* head) {
        if(head==NULL)return{};//判空
        ListNode *dummy = new ListNode(-1);
        dummy->next = head;
        ListNode *p=dummy->next;
        int len=0;
        while(p!=NULL){
            len++;
            p=p->next;
        }//计算出链表的结点个数len
                               //下面这里size的循环运算通过位运算除2，可以大大提升速度（否则会T的）
        for(int size=1;size<len;size<<=1){
            ListNode *cur=dummy->next;
            ListNode *tail=dummy;
            while(cur!=NULL){
                ListNode *left=cur;
                ListNode *right=cut(left,size);
                cur=cut(right,size);

                tail->next=merge(left,right);
                while(tail->next!=NULL)
                    tail=tail->next;
            }
        }
        return dummy->next;
    }
};