目录
一、序言
快速排序和归并排序是我认为很常用的两个排序，而很多人对此仍然存在一些疑问与不解，所以今天让我带大家重新回顾一下这两个排序的代码实现。
二、快速排序
1.介绍
快速排序的原理基于分治法的思想，通过递归地将一个数组分成两个（或更多）较小的子数组，直到子数组的大小为1或0，此时子数组自然是有序的。然后，算法将这些有序的子数组合并成一个大的有序数组，但在这个特定的情况下，由于子数组已经是有序的，并且它们是按照大小顺序排列的（一个子数组中的所有元素都小于另一个子数组中的所有元素），所以合并步骤实际上不需要进行任何操作，整个数组就已经是有序的了。
2.思路
快速排序思路：(先排序再递归)
Step1. 定义left,right作为双指针（这么说可能不准确，但大概就是这个意思），一个从头遍历，一个从尾遍历。
Step2. 选择数据中一个数为参考值（一般默认第一个数的值），这里记作target。
Step3. 让left,right对应数据的值分别与之进行比较
若left对应的值小于target就向后遍历，直到大于等于target时停下；
若right对应的值大于target就向前遍历，直到小于等于target时停下。
当left与right都停下时，交换left与right对应的数据的值。
Step4. 重复以上操作，直到两者相遇。
两者会相遇到此时的right处，我们以right为界，同样对其左右序列进行相同排序操作（递 归）。循环往复，直至排序成功。
3.代码实现
快排函数部分：
void quick_sort(int begin,int end)
{
if(begin >= end) return ; //注意
int left = begin;
int right = end;
int target = a[begin];
while(left < right)
{
while(a[left] < target) left++; //注意是while，而不是if（while在这里表示一直移动，直到不满足时才停止）
while(a[right] > target) right--;
if(left < right) swap(a[left],a[right]); //这里必须要再次强调left < right，这样就避免了最后相遇的情况
}
//递归操作，对right左右区间进行同样操作（此时right左边全小于target，右边全大于target）
quick_sort(begin,right);
quick_sort(right+1,end);
}完整代码：
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int a[N], n;
void quick_sort(int begin,int end)
{
if(begin >= end) return ;
int left = begin;
int right = end;
int target = a[begin];
while(left < right)
{
while(a[left] < target) left++;
while(a[right] > target) right--;
if(left < right) swap(a[left],a[right]);
}
quick_sort(begin,right);
quick_sort(right+1,end);
}
int main() {
scanf("%d", &n);
for (int i = 0; i < n; i++) scanf("%d", &a[i]);
quick_sort(0, n - 1);
for (int i = 0; i < n; i++) printf("%d ", a[i]);
return 0;
}三、归并排序
1.介绍
归并排序的基本思想是将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。
2.思路
归并排序--分治思想：（先递归再排序）
Step1. 定义tmp数组用于存放已经排好序的数据（放第一步主要是让后续思路更清晰）
Step2. 将原数组（我把它记作a[]）数据分成两半：左区间（begin,mid）与 右区间（mid+1，end）
Step3. 递归，分别对左右两区间进行同样操作（这里直接调用该函数）--这里其实也好理解：
因为归并排序是先分成两部分，这两部分再分别细分左区间和右区间，一直分到不能
分为止，然后再按小块排序，排完序后再不断合并进行整体排序
Step4. 建立i,j,k
i表示左区间起点；j表示右区间起点；k表示tmp数组下标，从最初（begin）开始
Step5. i处于左区间且j处于右区间（两区间的元素都还没全存入tmp数组）时，tmp数组用于存放 两者较小值，然后存放的值对应的i或j进行相应移动（i右移或j左移）
Step6. 当j不在右区间时或i不在左区间时（即某个区间的数全都已经排完序，存入tmp中了），
这时只需要把剩下那个区间的数挨个填进tmp数组后边就行了
Step7. 最后不要忘记将tmp数组的值赋给原数组（a[]）
3.代码实现
归并排序函数部分：
void merge_sort(int begin, int end) {
int tmp[N]; //定义tmp数组用来存放已经排好序的数据
if (begin >= end) return ; //注意
int mid = begin + end >> 1; //位运算 >> 等价于除以2，将数据（数组）分成两半:左（begin,mid）与 右（mid+1,end）
merge_sort(begin, mid); //先递归，对左右区间进行同样操作
merge_sort(mid + 1, end);
int i = begin, j = mid + 1, k = begin; //i,j分别初始化在左右区间起点处 ,k作为tmp数组序标，初始化为begin
while (i <= mid && j <= end) //循环条件：i在左区间 且 j在右区间（两个区间的数都还没排完序存入tmp数组中）
{
if (a[i] <= a[j])
tmp[k ++ ] = a[i ++ ]; //tmp数组用于记录a[i]与a[j]两者的较小值，较小值对应的i或j进行+1，每次赋值后k++
else
tmp[k ++ ] = a[j ++ ];
}
//j不在右区间时 或 i不在左区间时（即某个区间的数全都已经排完序，存入tmp中了），这时只需要把剩下那个区间的数挨个填进去就行
while (i <= mid) tmp[k ++ ] = a[i ++ ];
while (j <= end) tmp[k ++ ] = a[j ++ ];
for (int i = begin; i <= end; i ++ )
a[i] = tmp[i]; //不要忘，这样就将a[i]排好序了
}完整代码：
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int a[N], n;
void merge_sort(int begin, int end)
int tmp[N];
if (begin >= end) return ;
int mid = begin + end >> 1;
merge_sort(begin, mid);
merge_sort(mid + 1, end);
int i = begin, j = mid + 1, k = begin;
while (i <= mid && j <= end)
{
if (a[i] <= a[j])
tmp[k ++ ] = a[i ++ ];
else
tmp[k ++ ] = a[j ++ ];
}
while (i <= mid) tmp[k ++ ] = a[i ++ ];
while (j <= end) tmp[k ++ ] = a[j ++ ];
for (int i = begin; i <= end; i ++ )
a[i] = tmp[i];
}
int main() {
scanf("%d", &n);
for (int i = 0; i < n; ++ i) scanf("%d", &a[i]);
merge_sort(0, n - 1);
for (int i = 0; i < n; ++ i) printf("%d ", a[i]);
return 0;
}四、小结
以上就是我对于快速排序和归并排序的一些理解，希望能够帮助到你。明天将继续更新代码随想录训练营的打卡，希望我能够坚持下去。我是算法小白，但也希望终有所获。
标签：归并,right,end,int,begin,排序,快速,left From： https://blog.csdn.net/2303_79786049/article/details/140590520