排序算法-归并排序

妖狐艹你老母 2022-08-01 03:14 263阅读 0赞

归并排序也是一个比较快速的排序算法，其思想是运用分治的思想，先对要排序的数进行分，每次从中间分成两部分，然后知道分成最小，然后在把他们合起来，边合起来边排序，最后有序，每次分的复杂度是log（n），然后合起来变成有序的复杂度O（n），总的复杂度O（n\*logn），速度比较快，但是每次合并要占用额外O（n）的空间，如果用链表实现的话可以避免，同时归并排序可用来求逆序对。

比如给这样一组数  
3 5 2 10 4 6 7  
首先分 3 5 2 | 10 4 6 7  
继续分 3 | 5 2 | 10 4 | 6 7  
继续分 3 | 5 | 2 | 10 | 4 | 7  
然后开始合并，并排序  
第一次：3 | 2 5 | 4 10 | 6 7  
第二次： 2 3 5 | 4 6 7 10  
第三次：2 3 4 5 6 7 10

数组实现的版本：

#include <iostream>
    #include <cstdio>
    #include <vector>
    using namespace std;
    const int N = 1001000;
    int a[N];
    int b[N];
    void Merge(int l,int r)
    {
        if((r-l)==1 || l==r)
            return ;
        int mid = (l+r)/2;
        Merge(l,mid);
        Merge(mid,r);
        vector<int> tmp;
        int i = l,j = mid,cnt = 0;
        while(i<mid && j<r)
        {
            if(a[i]<=a[j])
            {
                b[cnt++] = (a[i]);
                i++;
            }
            else
            {
                b[cnt++] = (a[j]);
                j++;
            }
        }
        while(i<mid)
        {
            b[cnt++] = (a[i]);
            i++;
        }
        while(j<r)
        {
            b[cnt++] = (a[j]);
            j++;
        }
        for(int i=0;i<cnt;i++)
        {
            a[l+i] = b[i];
        }
    }
    int main()
    {
        //freopen("Input.txt","r",stdin);
        int n,k;
        while(~scanf("%d%d",&n,&k))
        {
            for(int i=0;i<n;i++)
                scanf("%d",&a[i]);
            Merge(0,n);
            for(int i=0;i<n;i++)
                printf("%d ",a[i]);
            for(int i=n-1;i>=(n-k);i--)
                printf("%d%c",a[i],i==(n-k)?'\n':' ');
        }
        return 0;
    }

链表实现的版本，不需要额外的内存:(提交到hdoj上面超时了，不知道为什么会慢)

#include <iostream>
    #include <cstdio>
    #include <vector>
    using namespace std;
    
    struct ListNode
    {
        int val;
        ListNode *next;
    };
    ListNode *Creat(int n)
    {
        ListNode *head = new ListNode;
        scanf("%d",&head->val);
        head->next = NULL;
        ListNode *p = head;
        n--;
        while(n--)
        {
            ListNode *tmp = new ListNode;
            scanf("%d",&tmp->val);
            tmp->next = NULL;
            p ->next = tmp;
            p = p->next;
        }
        return head;
    }
    int v[1010000];
    void print(ListNode *head)
    {
        int cnt = 0;
        while(head!=NULL)
        {
            v[cnt++] = (head->val);
            head = head->next;
        }
    }
    ListNode *Merge(ListNode *head)
    {
        if(head==NULL || head->next==NULL)
            return head;
        ListNode *fast = head,*flaw = head;
        while(fast->next!=NULL && fast->next->next!=NULL)
        {
            flaw = flaw->next;
            fast = fast->next;
            if(fast->next!=NULL)
                fast = fast->next;
        }
        fast = flaw->next;
        flaw->next = NULL;
        flaw = Merge(head);  //SB
        fast = Merge(fast);
        ListNode *root = new ListNode;
        ListNode *p = root;
        while(flaw!=NULL && fast!=NULL)
        {
            if(flaw->val<=fast->val)
            {
                p->next = flaw;
                flaw = flaw->next;
            }
            else
            {
                p->next = fast;
                fast = fast->next;
            }
            p = p->next;
    
        }
        while(flaw!=NULL)
        {
            p->next = flaw;
            flaw = flaw->next;
            p = p->next;
        }
        while(fast!=NULL)
        {
            p->next = fast;
            fast = fast->next;
            p = p->next;
        }
        p = root->next;
        delete[] root;
        return p;
    }
    void dele(ListNode *head)
    {
        while(head!=NULL)
        {
            ListNode *tmp = head;
            head = head->next;
            delete[] tmp;
        }
    }
    int main()
    {
    //    freopen("Input.txt","r",stdin);
        int n,k;
        while(~scanf("%d%d",&n,&k))
        {
            ListNode *head = Creat(n);
            head = Merge(head);
            print(head);
            dele(head);
            for(int i=n-1;i>=(n-k);i--)
                printf("%d%c",v[i],i==(n-k)?'\n':' ');
        }
        return 0;
    }