备考蓝桥杯【快速排序和归并排序】

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

---

前言

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

首先先写上几句话：献给坚持创作的我和点开这篇文章希望进步的你
1.当身边的一道道风景，变成了回忆 ，才忽然发现，风景依然在，人已是非少年，起初，我们揣着糊涂装明白，后来，我们揣着明白装糊涂。

2.人生百味，情最浓，人生繁华，淡最真，人生一路，一步有一步的风景，一程有一程的感悟，不论时光如何流转，有些东西不会改变，那就是对美好的追求，对真情的渴望，给他人一份善良，给自己一份淡然。

3.如果难过，就抬头望望天空吧，望着望着就忘了，它那么大，一定可以包容你的所有委屈。

4.人生几十年，酸甜苦辣咸，各种滋味都有，打开内心的窗，去呼吸一下外面的新鲜空气。别让自己活得太累。应当学着想开、看淡、学着不强求，学着深藏。适时放松自己，找寻宣泄，给疲倦的内心解解压。

5.关关难过关关过，夜夜难熬夜夜熬，悲喜自渡，他人难悟。悄悄崩溃，默默自愈。

​

​

快速排序：

题目：

给定你一个长度为 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;
}

归并排序：

题目：

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

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

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

输入格式

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

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

输出格式

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

数据范围

1≤n≤100000

输入样例：

5
3 1 2 4 5

输出样例：

1 2 3 4 5

解题分析：

这也是一道分治算法:

1.确定分界点

2.递归排序left,right【重点】

3.归并----合二为一

代码：

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

最后

十分感谢你可以耐着性子把它读完和我可以坚持写到这里，送几句话，对你，也对我：

1.太多的事，慢慢地就不能做了；太多的人，渐渐地就不见了。成长似乎是一个丢失的过程。青春，就是注定了要颠簸，要有眼泪和汗水，有委屈、不甘和失败。后来，慢慢知道一切该发生的就是会发生，一切会错过的就是会错过。

2.趁自己还不老，走自己想走的路。没有理由，不去闯！时间，抓起了就是黄金，虚度了就是流水；理想，努力了才叫理想，放弃了那只是妄想！努力，虽然不一定会获得，但不努力，就一定一无所获。

3.趁自己还不老，走自己想走的路。没有理由，不去闯！时间，抓起了就是黄金，虚度了就是流水；理想，努力了才叫理想，放弃了那只是妄想！努力，虽然不一定会获得，但不努力，就一定一无所获。

4.我一直以为人是慢慢变老的，其实不是，人是一瞬间变老的。

5.随着年龄的增长，我们愈加发现，或许我们并不是失去了一些人，而是更加懂得到底谁才是最重要的人。

​

最后如果觉得我写的还不错，请不要忘记点赞✌，收藏✌，加关注✌哦(｡･ω･｡)

愿我们一起加油，奔向更美好的未来，愿我们从懵懵懂懂的一枚菜鸟逐渐成为大佬。加油，为自己点赞！
​

​