1快速排序思想分治思想步骤1.确定分界点通常选q[l]q[(lr)/2]q[r]或者也可以随机一个位置。2.调整区间对于升序排序就是将小于分界点值的元素放到分界点左边大于的放到右边从而划分为左右两个区间。3.递归处理左右两边区间。Acwing 785.快速排序给定你一个长度为 n 的整数数列。请你使用快速排序对这个数列按照从小到大进行排序。并将排好序的数列按顺序输出。输入格式输入共两行第一行包含整数 n。第二行包含 n 个整数所有整数均在 1∼109 范围内表示整个数列。输出格式输出共一行包含 n 个整数表示排好序的数列。数据范围1≤n≤100000输入样例5 3 1 2 4 5输出样例1 2 3 4 5王道计算机版本的代码使用首元素作为分界点但是过不去这道题的所有样例/*快速排序王道版本代码 两个函数quicksort和partition quicksort用于左右递归partition用于划分其中一趟排序 */ int q[N];//用于存放输入数据 int n; int partition(int l,int r)//对当前区间调整调整结束后返回基准值最终下标 { //进行划分 int pxq[l];//选第一个元素作为基准值 while(lr) { while(lrq[r]px) r--; q[l]q[r]; while(lrq[l]px) l; q[r]q[l]; } //将基准值放入最终位置 q[l]px; return l; } void quickSort(int l, int r) { if(lr) return;//只有一个元素或者区间不合法时 int pivotpartition(l,r); //对基准值下标左右两侧的闭区间继续递归调整 quickSort(l,pivot-1); quickSort(pivot1,r); }代码思路使用中间值作为分界点/*快速排序 acwing版本使用中间元素作为分界点 */ #include iostream #include cstring #include algorithm using namespace std; const int N100005; int q[N];//用于存放输入数据 int n; void quick_sort(int l,int r) { if(lr) return; int xq[(lr)/2]; int il-1,jr1; while(ij) { do i; while(q[i]x); do j--; while(q[j]x); if(ij) swap(q[i],q[j]); } quick_sort(l,j); quick_sort(j1,r); } int main() { cinn; for(int i0;in;i) cinq[i]; quick_sort(0,n-1); for(int i0;in;i) coutq[i] ; return 0; }(2)归并排序思想每次将两个有序的序列合并成一个有序的序列步骤先分别左右递归到最底层再归并每一层归并结束后再返回上一层。需要开辟一个O(n)的辅助空间时间复杂度为O(nlogn)Acwing 787.归并排序给定你一个长度为 n 的整数数列。请你使用归并排序对这个数列按照从小到大进行排序。并将排好序的数列按顺序输出。输入格式输入共两行第一行包含整数 n。第二行包含 n 个整数所有整数均在 1∼109 范围内表示整个数列。输出格式输出共一行包含 n 个整数表示排好序的数列。数据范围1≤n≤100000输入样例5 3 1 2 4 5输出样例1 2 3 4 5代码思路#include iostream #include algorithm #include cstring using namespace std; const int N100005; int a[N],n; int tmp[N];//辅助空间 void merge_sort(int l,int r) { if(lr) return; int mid(lr)/2; merge_sort(l,mid);//递归左边 merge_sort(mid1,r); int il,jmid1; int k0; while(imidjr) { if(a[i]a[j]) tmp[k]a[i]; else tmp[k]a[j]; } while(imid) tmp[k]a[i]; while(jr) tmp[k]a[j]; //将合并后的序列放回原位置 for(int il,j0;ir;i,j) a[i]tmp[j]; } int main() { cinn; for(int i0;in;i) cina[i]; merge_sort(0,n-1); for(int i0;in;i) couta[i] ; return 0; }归并排序经典用法是求逆序对的数量Acwing 788.逆序对的数量给定一个长度为 n 的整数数列请你计算数列中的逆序对的数量。逆序对的定义如下对于数列的第 i 个和第 j 个元素如果满足 ij 且 a[i]a[j]则其为一个逆序对否则不是。输入格式第一行包含整数 n表示数列的长度。第二行包含 n 个整数表示整个数列。输出格式输出一个整数表示逆序对的个数。数据范围1≤n≤100000数列中的元素的取值范围 [1,1e9]。输入样例6 2 3 4 5 6 1输出样例5代码思路/*逆序对的数量 在归并排序合并升序序列的过程中对于左右两个升序序列 如果l[i]r[j]那么l[i1]...l[mid]肯定都大于r[j]也就相当于这些l的元素都和r[j]形成一次逆序对 这种情况就需要计数一次。 所以对整个排序过程中的逆序对出现情况进行计数最后输出结果 */ #include iostream #include cstring #include algorithm using namespace std; const int N100005; int a[N],n; long long cnt0;//注意逆序对可能会有很多这里要用longlong定义计数器 int tmp[N]; void merge_sort(int l,int r) { if(lr) return; int mid(lr)/2; merge_sort(l,mid); merge_sort(mid1,r); int il,jmid1; int k0; while(imidjr) { if(a[i]a[j])//这种情况前后不构成逆序对 tmp[k]a[i]; else//这种情况,a[i]~a[mid]都与a[j]构成逆序对 { cnt(mid-i1);//计数逆序对数量 tmp[k]a[j]; } } while(imid) tmp[k]a[i]; while(jr) tmp[k]a[j]; for(int il,j0;ir;i,j) a[i]tmp[j]; } int main() { cinn; for(int i0;in;i) cina[i]; merge_sort(0,n-1); coutcntendl; return 0; }