归并排序指针版及链表版

╰+攻爆jí腚メ 2023-07-06 13:02 1阅读 0赞

> **什么是归并排序**  
> 　　 归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。  
> 　　归并排序比较占用内存，但却是一种**效率高且稳定**的算法。其时间复杂度为 O(n log n) ，空间复杂度为 T（n)。其速度仅次于快速排序，为稳定排序算法，一般用于对总体无序，但是各子项相对有序的数列。  
> 　　个人觉得一般归并排序用于链表的排序有奇效！

> **思路**  
> 　　归并排序的主要思想是**分治**。  
> 　　主要过程是：  
> 1.将n个元素从中间切开，分成两部分。（左边可能比右边多1个数）  
> 2.将步骤1分成的两部分，再分别进行递归分解。直到所有部分的元素个数都为1。  
> 3.从最底层开始逐步合并两个排好序的数列为一个有序的数列。  
> ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTY1MjY5NQ_size_16_color_FFFFFF_t_70]  
> ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTY1MjY5NQ_size_16_color_FFFFFF_t_70 1]  
> ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTY1MjY5NQ_size_16_color_FFFFFF_t_70 2][]图片取自https://www.cnblog.com/chengxiao/p/6194356.html

**指针版：**

#include <stdio.h>
    #include <string.h>
    #include <stdlib.h>
    void sort(int x, int y, int *st);       //将数组分开
    void Link(int x, int mid, int y, int *st);      //将分开的数组排序连接
    int main()
    { 
        int n, i ,a[1001];
        scanf("%d", &n);
        for(i = 0; i < n; i++)
        { 
            scanf("%d", &a[i]);
        }
        Sort(0, n, a);
        for(i = 0; i < n-1; i++)
            printf("%d\t", a[i]);
        printf("%d\n", a[i]);
    }
    void Sort(int x, int y, int *st)
    { 
        if(y-x == 1)        //此时表示分的小数组中只有一个元素，则直接返回
            goto END;
        int mid = x+(y-x)/2;
        Sort(x, mid, st);
        Sort(mid, y, st);
        Link(x, mid, y, st);
        END: ;
    }
    void Link(int x, int mid, int y, int *st)
    { 
        int p = 0, *temp = (int *)malloc((y-x)*sizeof(int)), a = x, b = mid, i;     //建议此处申请内存，不然可能会出错（本人因为这错了很久都没发现）
        while(a < mid && b < y)
        { 
            if(*(st+a) < *(st+b))
            { 
                temp[p++] = *(st+a++);
            }
            else
            { 
                temp[p++] = *(st+b++);
            }
        }
        while(a < mid)          //如果符合条件，则说明是后半段先退出，需要把前半段直接接在后面，下同
        { 
            temp[p++] = *(st+a++);
        }
        while(b < y)
        { 
            temp[p++] = *(st+b++);
        }
        for(i = 0; i < p; i++)
        { 
            *(st+x+i) = *(temp+i);
        }
        free(temp);         //记得需要free
    }

**链表版：**  
　　其实链表版与指针版大概思路一样，只是些许改变。

#include <stdio.h>
    #include <string.h>
    #include <stdlib.h>
    typedef struct test
    { 
        int data;
        struct test *next;
    }TEST;
    TEST *Sort(TEST *head);
    TEST *GetMid(TEST *head);       //找中点，这是与上面不同之处
    TEST *Link(TEST *head, TEST *mid);
    int main()
    { 
        int n, i;
        TEST *t[100], *head;
        scanf("%d", &n);
        for(i = 0; i < n; i++)
        { 
            t[i] = (TEST *)malloc(sizeof(TEST));
            scanf("%d", &t[i]->data);
        }
        for(i = 0; i < n-1; i++)
        { 
            t[i]->next = t[i+1];
        }
        t[i]->next = NULL;
        head = Sort(t[0]);
        while(head->next != NULL)
        { 
            printf("%d\t", head->data);
            head = head->next;
        }
        printf("%d\n", head->data);
        return 0;
    }
    TEST *Sort(TEST *head)
    { 
        if(head->next == NULL)
            return head;
        TEST *mid = GetMid(head);
        head = Sort(head);
        mid = Sort(mid);
        return Link(head, mid);
    }
    TEST *GetMid(TEST *head)
    { 
        if(head->next == NULL)
            return head;
        TEST *q = head, *s = head, *t;
        while(q->next != NULL && q->next->next != NULL)
        { 
            q = q->next->next;
            s = s->next;
        }
        t = s->next;
        s->next = NULL;
        return t;
    }
    TEST *Link(TEST *head, TEST *mid)
    { 
        TEST *ret = NULL, *tail = NULL;
        while(head!=NULL && mid!=NULL)
        { 
            if(head->data < mid->data)
            { 
                TEST *temp = head->next;
                if(ret == NULL)
                { 
                    ret = tail = head;      //ret是为了记录连接后的链表的头
                    ret->next = NULL;
                }
                else
                { 
                    tail->next = head;
                    tail = tail->next;
                    tail->next = NULL;
                }
                head = temp;
            }
            else
            { 
                TEST *temp = mid->next;
                if(ret == NULL)
                { 
                    ret = tail = mid;
                    ret->next = NULL;
                }
                else
                { 
                    tail->next = mid;
                    tail = tail->next;
                    tail->next = NULL;
                }
                mid = temp;
            }
        }
        if(head == NULL)
            tail->next = mid;
        else
            tail->next = head;
        return ret;
    }

感谢师傅来访，技术不精，请勿吐槽，如有问题请留言。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTY1MjY5NQ_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/2020021821243759.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTY1MjY5NQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTY1MjY5NQ_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200218212458473.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTY1MjY5NQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTY1MjY5NQ_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200218212521315.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTY1MjY5NQ==,size_16,color_FFFFFF,t_70