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

---

前言

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

---

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

一、快速排序

1.1快速排序的知识讲解

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

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

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

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

• 两个指针ij不断在这里面移动

• 当指针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
• 递归排序leftright
• 归并,合二为一
  
  下面就讲解一下归并排序的大致思路
• 先比较两个指针所指向的元素谁大谁小
• 谁小就拿下来放到新的保存数组里面然后指针向后挪动一位依次类推
• 直到其中一个指针走向了终点的位置为止就可以把没有走完的直接补充到我们的保存数组里面

归并排序的原理动图

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.cn

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

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

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

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