快排+归并-Toy模板网

这篇具有很好参考价值的文章主要介绍了快排+归并。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

🥇快排

🎀快排题目

快排+归并

🎫快排代码实现

#include<iostream>
using namespace std;
const int N=100010;//定义一个只读变量
int a[N]={0};//开辟空间，定义全局变量，后来就不用传参了
void quicksort1(int l,int r)
{
    if(l>=r) return;
    int x=a[(l+r+1)/2];
    int i=l-1,j=r+1;
    while(i<j)
    {
        do i++;while(a[i]<x);
        do j--;while(a[j]>x);
        if(i<j) swap(a[i],a[j]);
    }
    quicksort(l,i-1);
    quicksort(i,r);
}
void quicksort2(int l,int r)
{
    if(l>=r) return;
    int x=a[(l+r+1)/2];
    int i=l-1,j=r+1;
    while(i<j)
    {
        do i++;while(a[i]<x);
        do j--;while(a[j]>x);
        if(i<j) swap(a[i],a[j]);
    }
    quicksort(l,j);
    quicksort(j+1,r);
    
    
}

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

🎊快排动图展示

快排+归并

🎆快排思想

快排：首先选取一个参照物，然后使用两个指针分别与他进行比较，需要左边的比他小，右边的比他大，如果不符和就交换；知道两个指针相等或者交错；接着进行递归，直到最后只剩下1个元素才停止

🏅🏅🏅代码讲解

(接下来的模版是需要记住的）
1.题目需要10^5的空间大小，我们为了方便多开辟10个空间
2.使用递归的时候先明确递归出口—l>=r
3.选取参照物—x=a[(l+r+1)/2]—为什么需要进行l+r+1呢，不能直接就r+l吗？？？
这是因为我们需要进行向上取整，如果是r+l会出现死递归的现象
4.我们定义两个变量i，j需要让i先指向第一个的前一个，j指向最后一个的后一个，然后开始的时候先让i++,j–然后再进行判断（记住就行了）

	//这种方法是跑不过去的，会出现很多的问题
    int i=l,j=r;
    while(i<j)
    {
        while(a[i]<x) i++;
        while(a[j]>x) j--;
        if(i<j) swap(a[i],a[j]);
    }

5.c++的同学可以直接使用swap函数（自带的），如果需要自我实现的话，需要注意传参的时候是传值还是传地址
6.交换之前需要进行判断，如果i<j才是需要进行交换的，如i=j是可以进行交换的，但是没有必要
7.（需要背过）

//这两个是模版

    quicksort(l,i-1);
    quicksort(i,r);


    quicksort(l,j);
    quicksort(j+1,r);

🥇归并

🎀归并题目

快排+归并

🎫归并代码实现

#include<iostream>
using namespace std;
const int N=100010;
    int nums[N];
    int tem[N];
void mergesort(int l,int r)
{
    if(l>=r) return ;
    int mid=l+r>>1;
    
    mergesort(l,mid),mergesort(mid+1,r);
    int k=0;
    int i=l,j=mid+1;
    while(i<=mid&&j<=r)
    {
        if(nums[i]<nums[j]) tem[k++]=nums[i++];
        else tem[k++]=nums[j++];
    }
    while(i<=mid) tem[k++]=nums[i++];
    while(j<=r) tem[k++]=nums[j++];
    for(int i=l,j=0;i<=r;i++,j++) nums[i]=tem[j];
}
int main()
{
    int n;
    cin>>n;
    for(int i=0;i<n;i++) cin>>nums[i];
    mergesort(0,n-1);
    for(int i=0;i<n;i++) cout<<nums[i]<<' ';
    
    
    return 0;
}

🎊归并动图

快排+归并

🎆归并思想

归并是从最小的部分开始进行排序，逐层排序，是每一层越来越有序，直到最后整体有序

🏅🏅🏅代码讲解

（模版需要记住哦）
1.这里我们只需要mid=l+r>>1 ,因为***+的优先级大于>>的优先级***，如果不清楚的同学可以加上括号
2.因为归并排序是先最小逐层变大，所以需要先递归；同时我们可以使用逗号表达式
3.我们需要定义一个额外的空间用来存储已经排好序的数组，
4.循环条件需要注意，一定是&&不能是||，因为如果是||，我们想象一下，如果一个区间已经遍历完了，另一个区间还在继续，那么这个已经遍历完的区间是不是还在继续遍历，那是不是就不是我们想要的结果了
5.我们进行判断，如果nums[i]<nums[j] 将nums[i]存入tem[k]，否则将nums[j]存入tem[k]；因为i++和++i的问题，我们只能使用这种，或者分开写