算法【快速排序和归并排序】

🌹作者:云小逸
📝个人主页:云小逸的主页
📝Github:云小逸的Github
🤟motto:要敢于一个人默默的面对自己，强大自己才是核心。不要等到什么都没有了，才下定决心去做。种一颗树，最好的时间是十年前，其次就是现在！学会自己和解，与过去和解，努力爱自己。==希望春天来之前，我们一起面朝大海，春暖花开！==🤟
👏专栏：C++👏 👏专栏：Java语言👏
👏专栏：C语言初阶👏👏专栏：数据结构👏

文章目录

前言
快速排序：
- 题目：
- 输入格式
- 输出格式
- 数据范围
- 输入样例：
- 输出样例：
- 解题分析：
- - 1.确定分界点：x=q[l],q[(l+r)/2],q[r],q[随机]
  - 2.调整范围：【重点】
  - 3.递归处理左右两端。
- 下面做一个动图便于你的理解：
- 注意事项：
- 代码：
归并排序：
- 题目：
- 输入格式
- 输出格式
- 数据范围
- 输入样例：
- 输出样例：
- 解题分析：
- - 1.确定分界点
  - 2.递归排序left,right【重点】
  - 3.归并—-合二为一
- 代码：
最后

前言

——————————————————————————————

快速排序：

题目：

给定你一个长度为 n 的整数数列。

请你使用快速排序对这个数列按照从小到大进行排序。

并将排好序的数列按顺序输出。

输入格式

输入共两行，第一行包含整数 n。

第二行包含 n 个整数（所有整数均在 1∼109 范围内），表示整个数列。

输出格式

输出共一行，包含 n 个整数，表示排好序的数列。

数据范围

1≤n≤100000

输入样例：

5
3 1 2 4 5

输出样例：

1 2 3 4 5

解题分析：

快排属于分治算法，这里将快排分为三个步骤：

1.确定分界点：x=q[l],q[(l+r)/2],q[r],q[随机]

2.调整范围：【重点】

分界点之前小于x,分界点之后大于x.

3.递归处理左右两端。

三个步骤中的重点是第二个【调整范围】
这里再详细讲解一下：

下面做一个动图便于你的理解：

注意事项：

边界点问题，非常重要！！！
边界点的取值问题：中点或者随机，不可以左端或者右端！！！

代码：

#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>

using namespace std;

const int N = 1e6 + 10;

int q[N];

void quick_sort(int q[], int l, int r)
{
    if (l >= r) return;
    int i = l - 1, j = r + 1;
    int x = q[(r + l) / 2];//中点
    //int x=rand()%(r-l+1)+1;
    //int rnd_idx = rand() % (r - l + 1) + l;
    //swap(q[l], q[rnd_idx]);
    // int x = q[l];
    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;
}

归并排序：

题目：