归并排序——主要思想分治

桃扇骨 2023-09-30 11:05 15阅读 0赞

### 归并排序——主要思想分治 ###

1.随机取其中的一个值，将其分为两边，最后两边分别进行递归排序

2.归并，把两个有序的序列合并成一个有序的序列

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIzOTM2MTcz_size_16_color_FFFFFF_t_70]

#include<iostream>
    using namespace std;
    
    const int N = 1e6 + 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, 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++];
        
        for(i=l,j=0;i<=r;i++,j++) q[i]=tmp[j];
    }
    
    int main(){
        
        scanf("%d",&n);
        for(int i=0;i<n;i++) scanf("%d",&q[i]);
        
        merge_sort(q,0,n-1);
        
        for(int i=0;i<n;i++) printf("%d ",q[i]);
        
        return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIzOTM2MTcz_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20190202134723164.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIzOTM2MTcz,size_16,color_FFFFFF,t_70

发表评论取消回复

表情：

评论列表（有 0 条评论，15人围观）

还没有评论，来说两句吧...

相关阅读

相关分治算法——快排 | 归并思想

文章目录一、快排思想 1. leetcode75. 颜色分类 2. leetcode912. 排序数组 3. leetco

心已赠人/ 2024年02月22日 03:42/ 0 赞/ 60 阅读

相关归并排序——主要思想分治

归并排序——主要思想分治 1.随机取其中的一个值，将其分为两边，最后两边分别进行递归排序 2.归并，把两个有序的序列合并成一个有序的序列 ![在这里插入图片描述][w

桃扇骨/ 2023年09月30日 11:05/ 0 赞/ 16 阅读

相关快速排序——主要思想是分治

快速排序——主要思想是分治分治算法的基本思想是将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立且与原问题性质相同。求出子问题的解，就可得到原问题的解。

小鱼儿/ 2023年09月30日 11:04/ 0 赞/ 5 阅读

相关十大排序算法-分治思想-归并排序&&快速排序(js实现)

文章目录一、分治思想二、归并排序 1.思路分析 2.排序过程演示 3.代码实现 4.复杂度分析

秒速五厘米/ 2022年11月18日 13:57/ 0 赞/ 69 阅读

相关分治法-归并排序

一、前言归并排序归并排序是建立在归并操作上的一种有效的排序算法，速度仅次于快速排序，为稳定排序算法，一般用于对总体无序，但是各子项相对有序的数列。该算法是采用分

落日映苍穹つ/ 2022年11月16日 05:47/ 0 赞/ 205 阅读

相关 422-分治算法-归并排序

分治算法-归并排序 ![在这里插入图片描述][d75c109a15d04a919e5595e0debff529.png] 对上面数据进行归并排序我们进行划分 !

绝地灬酷狼/ 2022年09月05日 04:05/ 0 赞/ 195 阅读

相关分治——归并排序

归并排序(merge sort)是经典算法了，采用了分治策略。归并排序把序列任意分为两部分，一般采用二分，分别递归（排序）后，再把两个有序序列合并为一个有序序列，即在划分

谁践踏了优雅/ 2022年06月15日 01:10/ 0 赞/ 242 阅读

相关归并排序（分治）

基本思想：归并排序（MERGE-SORT）是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成

曾经终败给现在/ 2022年06月10日 14:19/ 0 赞/ 237 阅读

相关【分治】归并排序

目录一、二路归并实现二、二路归并的一点优化三、原地归并实现四、二路归并的非递归实现五、在归并排序中使用直接插入排序 ----------------

曾经终败给现在/ 2022年04月02日 13:22/ 0 赞/ 255 阅读

相关分治法——归并排序

归并排序归并排序是成功应用分治法的完美例子，归并排序是按照记录在序列中的位置对序列进行划分。【问题】应用归并排序方法对一个记录序列进行升序排序。归并排序（m

￡神魔★判官ぃ/ 2021年06月22日 15:36/ 0 赞/ 495 阅读