本博客将讲述常见的几种排序算法
在日常码代码时，常常会用到排序，排序算法又有很多，每种排序都会有自己的特点和适用情况，
我在这将总结几种排序算法，废话少说，开始！
冒泡排序（bubble sort）
冒泡排序，因像水泡一样一个接一个地冒出水面（排序），而得名。
冒泡排序的思想是每次将最大的一次一次运到最右边，然后将最右边这个确定下来。再来确定第二大的，再确定第三大的.....
对于数组a[]，具体的来说，每次确定操作就是从左往右扫描，如果a[i]>a[i+1]，我们就执行swap(a[i],a[ i+1])将两项交换，然后再往右检查，这样可以找出最大的并将其丢到最右边。
第一次确定操作是将a[1]~a[n]中最大的放到a[n];
第二次确定操作是将a[1]~a[n-1]中最大的放到a[n-1]。
依此类推（类似地，如果你想先把最小的放到左边也是可以的)，时间复杂度为O(n^2)。由于排序过程中，数字像冒泡泡一样从左往右换过去，故名冒泡排序。可以多观看下面动图复制理解。
代码如下：
注意：外循环不需要n次，最后两个比一次即可。
内循环需要n-i次，其余i次前面循环已经比较不需要再进行比较
for(int i=1;i<n;++i)//注意是n，比较不需要比完，最后两个比一次即可
{
for(int j=1;j<=n-i;++j)//i的前面比较情况就已经将最大或最小的选出，因此不需要到n次
{
if(a[j]>a[j+1])
swap(a[j],a[j+1]);
}
}选择排序（select sort）
选择排序的思想和冒泡排序类似，是每次找出最大的然后直接放到右边对应位置，然后将最右边这个确定下来（而不是一个一个地交换过去)。
再来确定第二大的，再确定第三大的....
对于数组a[]，具体的来说，每次确定操作（假设当前要确定的是i位置)就是从左向右扫描，计算出
最大元素的下标max_id，最后执行一次swap(a[max_id],a[i])将两项交换即可。
第一次确定操作是将a[1]~a[n]中最大的放到a[n];
第二次确定操作是将a[1]~a[n-1]中最大的放到a[n-1]。
类推（类似地，如果你想先把最小的放到左边也是可以的)，时间复杂度为O(n^2)。
注意比较范围是所有元素，这点与冒泡排序不同。因为要挑选而不是比较。
//i表示当前位置
for (int i = n; i >= 1; --i)
{
int max_id = 1;//初始化为1
//j从左向右扫求出max_id
for (int j = 1; j <= i; ++j)
{
if (a[j] > a[max_id])
max_id = j;
}
swap(a[max_id], a[i]);
}插入排序（insert sort）
插入排序是一种简单直观的排序算法，其基本思想是将待排序的元素逐个插入到已排序序列的合适
位置中，使得已排序序列逐渐扩大，从而逐步构建有序序列，最终得到完全有序的序列。
它类似于打扑克牌时的排序方式，将一张张牌插入到已经有序的手牌中。时间复杂度O(n^2)
插入排序一般用双重循环来实现。
初始时，我们认为长度为1的数组a[1]是有序的(显然)，然后将a[2]插入到合适的位置，使得a[1~2]有序,然后将a[3]插入，使得a[1~3]有序....直至a[1 ~n]有序。
for (int i = 2; i <= n; ++i)
{
//此时[1，i-1]已经为有序的数组
int val = a[i], j;
//将val与a[j-1]比较
//如果val<a[j-1]就将a[j-1]往后移移动一格
//给val留出位置
for (j = 1; j > 1 && val < a[j - 1]; --j)
{
a[j] = a[j - 1];
}
//当循环跳出时，j=1或valL>=a[j]，且此时a[j]已经向后移动一位
//此时的j为给val腾出的位置
a[j] = val;
}快速排序(quick sort)
快速排序是一种基于分治法的排序方法，原理是将一个数组分成两个子数组，其中一个子数组的所
有元素都小于另一个子数组的元素，然后递归地对这两个子数组进行排序。
快速排序的思想是通过不断地将数组分成两个子数组，递归地对子数组进行排序，最终得到一个有
序的数组。这个过程通过选择合适的基准和分区操作来实现。
快速排序拥有更好的时间复杂度O(nlogn)，且不需要额外空间。
下列是快速排序的代码
代码注解：快速排序的递归主体QuickSort()，传入参数为要排序的数组和区间的左右端点。
Partition函数会将数组a[1]~ a[r]这个区间中某个基准数字放到正确的位置并将这个位置返回。
在确定了mid的位置之后，可以保证a[1]~ a[mid - 1]都<a[mid]< a[mid+1]~a[r]，于是只需要将左右两边分别向下递归地排序即可。
Parition函数(分区函数)，用于将比pivot小的放到左边，大的放到右边，最后返回pivot所处的位置。
int Partition(int a[], int l, int r)//分区函数
{
//设a[r]为基准，这一次partition会将a[r]放在正确位置上
int pivot = a[r];
//设这两个下标i,j分别从l,r开始向中间走
int i = 1, j = r;
while (i < j)
{
while (i < j && a[i] <= pivot)i++;
//从上面循环出来后有i>=j或a[i]>pivot(说明找到了需要交换的位置)
while (i < j && a[j] >= pivot)j--;
//从上面循环出来后有i>=j或a[j]<pivot(说明找到了需要交换的位置)
//如果i<j说明存在a[j]<pivot,否则就是a[r]<=pivot，a[i]>=pivot
if (i < j) swap(a[i], a[j]);
else swap)(a[i], a[r]);
}
return 1;
}
void QuickSort(int a[], int l, int r)
{
if (l < r)//合法区间
{
int mid = Partition(a, l, r);
QuickSort(a, l, mid - 1);
QuickSort(a, mid+1, r);
}
}归并排序(merge sort)
归并排序和快速排序类似，也是一种基于分治法的排序方法。
原理是将一个数组分成两个子数组，将子数组向下递归的排序后（当数组中仅有一个元素值无需再
排序了，直接返回)，得到两个有序数组，然后进行O(n)的合并，最终合并成有序的原数组。
快速排序拥有较好的时间复杂度O(nlogn)，但需要额外的空间用于合并数组。
代码如下
void MergeSort(int a[], int l, int r)
{
if (l == r)return;//区间为1，直接返回
int mid = (l + r)/2;//注意这里会默认向下取整
MergeSort(a, l, mid);
MergeSort(a, mid+1, r);
//排序完成后a[l,mid]和a[mid+1,r]都是分别有序的
//将a[l,r]两部分一个个地放入到b[l,r]
int pl = l, pr = mid + 1, pb = l;//pl左半边下标，pr右半边下标,pb新数组下标
while (pl < mid || pr <= r)
{
if (pl > mid)
{
//左半边已经放完
b[pb++] = a[pl++];
}
else if (pr > r)
{
//右面已经放完
b[pb++] = a[pl++];
}
else
{
//两面都还有元素，取小的放到b中
if (a[pl] < a[pr])
b[pb++] = a[pl++];
else
b[pb++] = a[pr++];
}
}
//完成后复制回去
for (int i = l; i <= r; ++i)
a[i] = b[i];
}注明：本博客图片来源自网络，如有侵权，联系本人删除，谢谢！
少年没有乌托邦，心向远方自明朗！
如果这个博客对你有帮助，给博主一个免费的点赞就是最大的帮助❤
欢迎各位点赞，收藏和关注哦❤
如果有疑问或有不同见解，欢迎在评论区留言❤
后续会继续更新大连理工大学相关课程和有关算法的内容和代码
点赞加关注，学习不迷路，好，本次的学习就到这里啦！！！
我们下次再见喽！
标签：常用,int,mid,++,算法,数组,排序,pl From： https://blog.csdn.net/b19839356939/article/details/137052035