7.25 C/C++蓝桥杯 |排序算法【下】

接上文的冒泡排序和选择排序：7.24 C/C++蓝桥杯 | 排序算法-CSDN博客

插入排序

  插入排序，类似打牌的时候排牌的操作，将新的牌  插入到  前边已经有序的牌之中。

代码：

结果：

快速排序

取其中一个值x，大于x放到x右边，小于x放到x左边，递归。

怎么放？ 基准数x，从两边同时向中间扫，左边大于x的与右边小于x的元素交换位置

代码：

归并排序 

1. 分解：将数组不断二分，直到每个子数组只包含一个元素
2. 合并：将已排序的子数组合并，形成更大的有序数组

#include<bits/stdc++.h>
uisng namespace std;
const int N=1e5+9;
int a[N];
int main(){ios::sysnc_with_stdio(o),cin.tie(0),const.tie(0);int n;cin>>n;for(int i=1;i<=n;i++)cin>>a[i];MergeSort(a[],1,n);for(int i = 1; i <= n; i ++)cout<<a[i] << ' ';}
void MergeSort(int a[], int l,int j){if(l==r)return ;//l=r  即当区间大小为1时，直接返回 ;也就是分解？？int mid=(l+r)/2;MergeSort(a,l,mid);MergeSort(a,mid+1,r);int pl=l,pr=mid+1,pb=1;//起始索引 //有一边没有放完 while(pl<=mid||pr<=r){if(pl > mid){b[pb++]=a[pr++];} else if(pr > r){b[pb++]=a[pl++];}else{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];
}
//先递归进去，再回溯出来 

有空再更新