【algorithm】算法基础课---排序算法（附笔记 | 建议收藏）

🚀write in front🚀
📝个人主页：认真写博客的夏目浅石.
🎁欢迎各位→点赞👍 + 收藏⭐️ + 留言📝
📣系列专栏：AcWing算法学习笔记
💬总结：希望你看完之后，能对你有所帮助，不足请指正！共同学习交流 🖊
✉️如果无聊的话，就来逛逛我的博客栈吧stack-frame.***

前言

之前其实做过关于快速排序以及归并排序的博客笔记，但是我觉得我讲解的是不到位，所以我打算重新写一篇博客来帮助自己和大家梳理一下这两个算法模板以及配套的习题。

其实就是把元素放到x的两侧

一、快速排序

1.1快速排序的知识讲解

快速排序的核心思想：基于分治
快速排序主要的内容就是：

• 确定分界点：q[L],q[(L+R)/2],q[R] 其实就是分为左边界，中间值和右边界，甚至随机一个数

• 调整区间，其实就是把元素放到x的两侧

• 递归处理左右两段
  
  下面就是具体讲解步骤二的调整区间
  

• 两个指针，i，j不断在这里面移动

• 当指针i指向的元素<=x的时候就指针向右移动，同理指针j遇到>=x的时候就指针向左移动

• 当i指针指向的元素>=x的时候停下来，等到j指针指向的元素<=x的时候就也停下来

• 最后使得这两个元素进行swap交换一下

以上就是快速排序的基础知识啦，下面就要讲解一些习题来巩固和练习我们所讲解的知识点啦

快排思想图:

1.2快速排序的习题讲解

C语言实现：

#include<stdio.h>
int arr[100010];

void quick_sort(int arr[],int l,int r)
{
    if(l>=r) return;
    int i=l-1,j=l+1,x=arr[l];
    while(i<j)
    {
        do i++;while(arr[i]>x);
        do j--;while(arr[j]<x);
        if(i<j)
        {
            int tmp=arr[i];
            arr[i]=arr[j];
            arr[j]=tmp;
        }
    }
    quick_sort(arr,l,j);
    quick_sort(arr,j+1,r);
    
}

int main()
{
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++) scanf("%d",&arr[i]);
    
    quick_sort(arr,0,n-1);
    
    for(int i=0;i<n;i++) printf("%d ",arr[i]);
    
    return 0;
}

C++实现：

#include <iostream>

using namespace std;

const int N = 1000010;

int q[N];

void quick_sort(int q[],int l,int r)
{
    if (l>=r) return;

    int i=l-1, j=r+1,x=q[l+r>>1];
    while (i<j)
    {
        do i++; while (q[i]<x);
        do j--; while (q[j]>x);
        if (i<j) swap(q[i], q[j]);
    }

    quick_sort(q,l,j);
    quick_sort(q,j + 1,r);
}

int main()
{
    int n;
    scanf("%d", &n);

    for (int i=0; i<n; i++) scanf("%d", &q[i]);

    quick_sort(q,0,n-1);

    for (int i=0; i<n;i ++) printf("%d ", q[i]);

    return 0;
}

#include<stdio.h>
void quick_sort(int arr[],int l,int r)
{
    if(l>=r) return;
    int i=l-1,j=r+1,x=arr[l];
    while(i<j)
    {
        do i++;while(arr[i]<x);
        do j--;while(arr[j]>x);
        if(i<j)
        {
            int tmp=arr[i];
            arr[i]=arr[j];
            arr[j]=tmp;
        }
    }
    quick_sort(arr,l,j);
    quick_sort(arr,j+1,r);
}
int main()
{
    int arr[100010];
    int n,k;
    scanf("%d %d",&n,&k);
    for(int i=0;i<n;i++) scanf("%d",&arr[i]);
    
    quick_sort(arr,0,n-1);
    
    for(int i=0;i<n;i++) 
    {
        if(i+1==k) printf("%d",arr[i]);
    }
    return 0;
}

其实C++和这个差不多，这里不再赘述了。

1.3对于快排的总结

其实就是自己要多练习几遍，反复敲打上几次就可以啦，然后隔一段时间再写一次看看自己是否可以再次写出来这个模板。

二、归并排序

2.1归并排序的知识讲解

归并排序的核心思想：基于分治
归并排序主要的内容就是：

• 确定分界点mid=（left+right）/2
• 递归排序left，right
• 归并,合二为一
  
  下面就讲解一下，归并排序的大致思路：
• 先比较两个指针所指向的元素谁大谁小
• 谁小就拿下来放到新的保存数组里面，然后指针向后挪动一位，依次类推
• 直到其中一个指针走向了终点的位置为止，就可以把没有走完的直接补充到我们的保存数组里面

归并排序的原理动图：

2.2归并排序的习题讲解

#include<stdio.h>
const int N=100010;
int arr[N],tmp[N];

void merge_sprt(int arr[],int l,int r)
{
    if(l>=r) return;
    
    int mid=(l+r)/2;
    merge_sprt(arr,l,mid),merge_sprt(arr,mid+1,r);
    
    int i=l,j=mid+1,k=0;
    while(i<=mid&&j<=r)
    {
        if(arr[i]<=arr[j]) tmp[k++]=arr[i++];
        else tmp[k++]=arr[j++];
    }
    while(i<=mid) tmp[k++]=arr[i++];
    while(j<=r) tmp[k++]=arr[j++];
    
    for(int i=l,j=0;i<=r;i++,j++) arr[i]=tmp[j];
    
}
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++) scanf("%d",&arr[i]);
    merge_sprt(arr,0,n-1);
    for(int i=0;i<n;i++) printf("%d ",arr[i]);
    return 0;
}

2.3对于归并的总结

主要对于逆序对问题很重要归并排序。

总结

今天重新写了一篇关于AcWing算法基础课的一篇博客，其实我第一次看的时候会觉得很难，但是今天又看了一遍，发现，简单了很多，或许我们曾经不会的，或许以后就会慢慢掌握，希望遇到困难的时候第一想到的不是退缩和放弃，而是拼尽全力试一试看看到底自己能不能行。

我是夏目浅石，希望和你一起学习进步，刷题无数！！！希望各位大佬能一键三连支持一下博主，hhhh~我们下期见喽

如果无聊的话，就来逛逛我的博客栈吧stack-frame.***

✨$原创不易，还希望各位大佬支持一下$

👍 $点赞，你的认可是我创作的动力！$

⭐️ $收藏，你的青睐是我努力的方向！$

✏️ $评论，你的意见是我进步的财富！$