归并排序是一种经典的排序算法，适用于各种不同场景和数据类型的排序需求。它具有以下使用背景和优势：
-
通用性：归并排序适用于各种不同类型的数据结构和数据类型，包括数组、链表、字符串等。它可以对任意长度的序列进行排序。
-
稳定性：归并排序是一种稳定的排序算法，即在排序过程中相等的元素的相对位置不会改变。这对于某些应用场景很重要，比如需要保留原始数据中相同元素的顺序。
-
高效性：尽管归并排序的时间复杂度为O(nlogn)，但它在实践中具有较高的效率。由于它采用分治法的思想，将大规模问题分解为小规模问题进行处理，因此适用于大型数据集的排序操作。
-
可读性和可理解性：归并排序的实现相对简单，容易理解。它的核心思想是将序列分成更小的部分，然后再合并排序得到有序序列，这个过程直观易懂。
-
外部排序：由于归并排序的特性，使其非常适合进行外部排序。外部排序指的是当数据量太大以至于无法一次性全部加载到内存中进行排序时，使用归并排序分阶段地进行排序。
总而言之，归并排序是一种通用、稳定且高效的排序算法，适用于各种数据类型和场景。无论是在学术研究领域还是实际应用中，归并排序都是一个重要的工具。
学习目标:
分治算法引入：
斗众如斗寡，形名是也”这句话的意思，可以通过分而治之的思考，将帅管理几个关键的负责人，这些负责人然后再管理下一级的负责人，下一级的负责人继续管下面的人，这样管理大军队就跟管理几个人一样简单
通过唐朝的三省六部制继续让学生理解分而治之的思想：
唐朝的三省六部制，皇帝掌管门下省，尚书省，中书省，然后尚书省管理吏部、礼部、兵部、刑部、民部、工部等六部，然后这六个部又有自己的负责人，实现了分而治之的思想；
在c++中，也有相同的思想就是分治思想；
分治算法：
分治算法的实现步骤。“分”而“治”之，先“分”后“治”。 分就是指把一个复杂的问题分解成很多规模较小的子问题，然后解决这些子问题。 治就是把解决的子问题合并起来，这样大问题就解决了。
分治算法的经典应用：归并排序
归并排序的思想，首先先把一个无序的数组按照某一方法去拆分，分成若干个子序列，再按照一定的顺序各自排列，然后再归并到一起，使得归并后依然是有序的 。
归并排序算法可以利用递归的思想去实现。
示例：分
继续
最后一层 数组一直拆到只剩下一个元素的时候，停止。
完成了分的阶段，接下来再来看看治的阶段。
其余单个都是如此合并，重点在每组有多个数的时候的合并；
并过程。3大于1.于是把1填入原数组的第一个位置，再比较3和2，还是2小就填入2；
然后6和3比，填入3,4和6比，填入4,5和6比填入5，7和6比填入6，以此类推；
练习：归并排序的思想：划分 + 合并。将原序列划分为问题规模为 1 ，再陆续合并子数组。选B
练习题：单层分的代码：
1、结束条件:序列只有一个元素，就不用再划分：l==r
2、mid将数组分为左右两半部分，是区间的中间点，左半部分为l~mid ：int i = l; i <= mid; i++
3、右半部分为mid+1~r ：int i = mid + 1; i <= r; i++
4、Divide(l , mid);
5、Divide(mid + 1 , r);29
单次合并的练习：
1、循环的条件:两个序列的左端点不会超过各自的末尾 ：i <= n && j <= m
2、比较每一个位置的值，谁小，谁存入结果数组，同时左端点下标右移 ：a[i] <= b[j]
3、循环结束，需判断两个序列谁还有剩余，把剩余的数全部放入结果数组 ：i <= n
4、j <= m
综合练习：归并排序：
过程：
不断划分，但因为不止分一次，也不知道分多少次，所以用递归：
每次划分数组时，都是对半分，那么我们可以创建一个函数，功能主要是用来划分。我们可以根据数组的左右两端下标，确定待划分数组的端点，这样我们也能知道中间点mid，也就能知道左边序列的端点是l到mid，右边序列的端点就是mid加1到r。如果l等于r，就说明数组中只有一个元素了，不能再划分。所以如果l小于r，可以进行划分
递归划分：排序的递归代码，划分左右边数组，先将区间l到r分成两边，mid=(l+r)/2，然后递归左右区间
合并，也不止合并一次，并且合并时要借助另一个数组存入每次合并的数；
主流程
归并排序
【思路分析】
本题使用归并排序，定义 MergeSort 函数递归的进行划分并且使划分后合并的序列有序
在 MergeSort 函数中，int mid = (l + r) / 2，l 和 r 分别为序列存在 a 数组的第一个位置和最后一个位置，mid 为中间的位置，对前半段进行划分：
MergeSort(a, l, mid);，再对后半段进行划分：MergeSort(a, mid + 1, r);，然后再将前后两段有序序列合并
[l1,r1]，[l2,r2] 为两个序列的范围。
while循环条件为：l1<= r1 && l2 <= r2，在循环中：
如果 a[l1]<=a[l2]，表示 a[l1] 的值在 a[l2] 前面，将
a[l1] 的值赋给 a[cnt]，l1++，cnt++，下标加 1 进行下一轮比较。
否则 a[l2] 的值在 a[l1] 前面，将 a[l2] 的值赋给 c[cnt]，l2++，cnt++，下标加 1 进行下一轮比较。
循环结束后，两个序列可能存在剩下的元素没有赋值，将剩下的元素用 for 循环存在 c 数组中。
1、定义变量 n 和数组
2、划分，左端点为 1，右端点为 n，递归处理
2.1、递归的结束条件:只有一个数，就不用再递归下去，直接返回
2.2、找到中间位置，递归处理左半部分，递归处理右半部分
3、合并，两个序列分别为[l,mid] 和 [mid+1,r]，从最左边开始，依次比较，小的数放入结果数组c，下标右移
3.1、判断两个序列是否有剩余，有剩余的，全部放入结果数组 c
4、把结果数组 c 重新赋给 a 数组
5、输出a数组
【参考代码】
#include<iostream>
using namespace std;
int n , a[1010] , temp[1010];
void MergeSort(int l , int r)
{
//2.1、递归的结束条件:只有一个数，就不用再递归下去，直接返回
if(l == r)
return;
//2.2、找到中间位置，递归处理左半部分，递归处理右半部分
int mid = (l + r) / 2;
MergeSort(l , mid);
MergeSort(mid + 1 , r);
//3、合并，两个序列分别为[l,mid] 和 [mid+1,r]，从最左边开始，依次比较，小的数放入结果数组c，下标右移
int i = l, j = mid + 1, k = l;
while(i <=mid && j <= r)
{
if(a[i] <= a[j])
temp[k++] = a[i++];
else
temp[k++] = a[j++];
}
//3.1、判断两个序列是否有剩余，有剩余的，全部放入结果数组 c
while(i <= mid)
temp[k++] = a[i++];
while(j <= r)
temp[k++] = a[j++];
//4、把结果数组 c 重新赋给 a 数组
for(int i = l; i <= r; i++)
a[i] = temp[i];
//5、输出a数组
for(int i = 1; i <= n; i++)
cout << a[i] << " ";
cout << endl;
}
int main()
{
//1、定义变量 n 和数组
cin >> n;
for(int i = 1; i <= n; i++)
cin >> a[i];
//2、划分，左端点为 1，右端点为 n，递归处理
MergeSort(1 , n);
return 0;
}
View Code
快速排序
快速排序（Quick Sort）是一种常用且高效的排序算法，适用于各种不同场景和数据类型的排序需求。它具有以下使用背景和优势：
-
高效性：快速排序是一种分治法的排序算法，通过选择一个基准元素，并将序列划分为两个子序列，然后分别对子序列进行排序。它的平均时间复杂度为O(nlogn)，在实践中表现出较高的效率。
-
内部排序：快速排序适用于内存中的排序操作，其中所有的数据可以一次性加载到内存中进行排序。这使得它在排序相对较小的数据集时非常高效。
-
原地排序：快速排序可以在原始数组上进行操作，而不需要额外的辅助空间。只需要通过指针或索引来交换元素位置，从而节省了存储空间的使用。
-
适应性：快速排序对于大多数输入数据都表现良好，在实践中具有很好的适应性。它在处理已经部分有序的数组时仍然能够保持较好的性能。
-
可扩展性：快速排序可以通过选择不同的基准元素和优化策略来提高其性能和稳定性。例如，随机选择基准元素可以避免最坏情况的发生，并提高排序算法的平均性能。
总之，快速排序是一种常用且高效的排序算法，适用于各种数据类型和场景。它在内存中的排序操作、具有原地排序特性以及良好的适应性等优势，使得它成为了实际应用中常用的排序算法之一。
定义 QuickSort 函数对 a 数组中1~n 的元素进行升序排序，定义 partition 函数 以第一个元素为枢轴进行划分，并返回划分后枢轴的下标位置。
QuickSort 中：当 l>=r 时只有一个元素，不能划分，递归结束。pop 为划分后枢轴的下标位置，等于 partition(a, l, r);，划分结束输出整个 a数组，然后继续对枢轴左边的元素进行划分：QuickSort(a, l, pos - 1);，再对枢轴右边的元素进行划分：QuickSort(a, pos + 1, r);。
partition 中定义 l、r为左右指针，k 为枢轴元素，等于 a[l]，然后利用while 循环将比 k 小的元素放在 k 的左边，比 k 大的元素放在 k 的右边，循环结束返回枢轴的位置 i。
1、定义变量 n 和数组，输入
2、快速排序，递归处理
2.1、结束条件
2.2、找到一趟快速排序后，记录枢轴的位置
2.3、输出一次的结果
2.4、递归处理左右两边
3、找枢轴的位置，保证枢轴左边的都比枢轴小，枢轴右边的都比枢轴大
3.1、l和r分别为左右端点，k为枢轴
3.2、右边的元素比枢轴大，右端点左移
3.3、左边的元素比枢轴小，左端点右移
【参考代码】
#include <iostream>
using namespace std;
const int N = 1e3 + 10;
int a[N];
int n;
int partition(int a[], int l, int r)
{
//3、找枢轴的位置，保证枢轴左边的都比枢轴小，枢轴右边的都比枢轴大
//3.1、l和r分别为左右端点，k为枢轴
int k = a[l]; //枢轴
while (l < r)
{
//3.2、右边的元素比枢轴大，右端点左移
while (l < r && a[r] >= k)
r--;
a[l] = a[r];
//3.3、左边的元素比枢轴小，左端点右移
while (l < r && a[l] <= k)
l++;
a[r] = a[l];
}
a[l] = k;
return l; //返回枢轴位置
}
//数组 a 的[l,r] 排序(升序）
void QuickSort(int a[], int l, int r)
{
//2.1、结束条件
if (l >= r) return; //只有一个元素，不能划分，返回
//2.2、找到一趟快速排序后，记录枢轴的位置
int pos = partition(a, l, r);//划分后枢轴的位置
//2.3、输出一次的结果
for(int i = 1; i <= n; i++)
cout << a[i] << " ";
cout << endl;
//2.4、递归处理左右两边
QuickSort(a, l, pos - 1);
QuickSort(a, pos + 1, r);
}
int main()
{
//1、定义变量 n 和数组，输入
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i];
//2、快速排序，递归处理
QuickSort(a, 1, n);
return 0;
}
View Code
参考此视频复习快排思路：https://www.bilibili.com/video/BV1vP411g7J3/?spm_id_from=333.337.search-card.all.click
初赛知识：
练习题：考察计算机发展历史，计算机最早应用的领域正是数值计算，世界上最早的计算机——美国的ENIAC的设计初衷是进行数值分析，计算导弹弹道轨迹。
总结：
作业讲解：系统上有的
标签：10,归并,进阶,int,mid,U3,枢轴,数组,排序 From： https://www.cnblogs.com/jayxuan/p/17967961