前言
本章节和大家一起学习排序算法中的快速排序和归并排序,基本思想我就不再赘述,前面章节有讲：＜＜算法很美＞＞——(三)十大排序算法(上)_skeet follower的博客-CSDN博客
快速排序算法模板
void quick_sort(int q[], int l, int r) { //结束条件 if (l >= r) return; //子问题 int i = l - 1, j = r + 1, x = q[l + r >> 1]; while (i < j) { do i ++ ; while (q[i] < x); do j -- ; while (q[j] > x); if (i < j) swap(q[i], q[j]); } //递归处理子问题 quick_sort(q, l, j), quick_sort(q, j + 1, r); }
代码深入理解:
问题代码1:
1. while (q[i] < x) i++; 2. while (q[j] > x) j++;
这个代码当q[i]和q[j]都等于x时,i和j不会更新 这个代码会陷入死循环.
问题2:结束条件能否写成l==r?
答案是可以的，这里是个人习惯问题,写成l==r或l>=r都是没问题的
问题3:while(q[i]<x)和while(q[i]>x)这里能否写成while(q[i]<=x)和while(q[i]>=x)？
答案:不能;我们来想一种很特殊的情况，假设数字全部相等,i会一直往右走,i会自增到r+1,继续执行q[i]<x就会造成下标越界.假设你数组开的足够长,这里不会报错，但是会一直循环下去,造成内存超限制
问题4:最后一句能否改用quick_sort(q, l, j-1), quick_sort(q, j, r)？
答案:不能;当mid不加1时，区间划分为：L~mid和mid+1~R，反之L~mid-1和mid~R。
换而言之，知道什么时候mid+1就能推算出区间划分。
+1时，向上取整，是为了mid不取到左边界，什么时候不能取左边界？用左边界划分时~
同理用右边界划分时不能取到右边界，故此向下取整~
根据上面的推论，当x = q[l + r >> 1]时即mid向下取整了，那么就不能选取i作为边界~因此边界为L~j和j+1~R
注意quick_sort(q, l, j-1), quick_sort(q, j, r)可能会造成无线划分
这里的边界思想二分法也要用到，所以大家务必掌握下
讲到这里，我就用i做划分写一下代码
void quick_sort(int q[], int l, int r) { if(l >= r) return; int i = l - 1, j = r + 1, x = q[l + r + 1 >> 1];//注意是向上取整,因为向下取整可能使得x取到q[l] while(i < j) { do i++; while(q[i] < x); do j--; while(q[j] > x); if(i < j) swap(q[i], q[j]); } quick_sort(q, l, i - 1), quick_sort(q, i, r);//这里是向上取整,避免取到左边界，以左边界划分 }
到这里快排的模板基本就结束了, 可以解决不保证百分百，但是也有百分之九十的快排问题,大家可以把模板理解加记忆,下面做两个题帮助大家记忆
快速排序
#include<iostream> using namespace std; #define N 100001 int tmp[N]; void quicksort(int tmp[],int left,int right) { if(left>=right) { return ; } int i=left-1,j=right+1,keyi=tmp[left+right+1>>1]; while(i<j) { do i++;while(tmp[i]<keyi); do j--;while(tmp[j]>keyi); if(i<j)swap(tmp[i],tmp[j]); } quicksort(tmp,left,i-1),quicksort(tmp,i,right); } int main() { int n; scanf("%d",&n); for(int i=0;i<n;i++) { scanf("%d",&tmp[i]); } quicksort(tmp,0,n-1); for(int i=0;i<n;i++) { printf("%d ",tmp[i]); } return 0; }
第k个数
#include<iostream> using namespace std; #define N 100001 int a[N]; void quicksort(int a[],int left,int right) { if(left>=right){ return ; } int i=left-1,j=right+1,keyi=a[left+right>>1]; while(i<j) { do i++;while(a[i]<keyi); do j--;while(a[j]>keyi); if(i<j)swap(a[i],a[j]); } quicksort(a,left,j),quicksort(a,j+1,right); } int main() { int n,m; scanf("%d %d",&n,&m); for(int i=0;i<n;i++) { scanf("%d",&a[i]); } quicksort(a,0,n-1); printf("%d",a[m-1]); return 0; }
归并排序算法模板
void merge_sort(int q[], int l, int r) { //结束条件 if (l >= r) return; //分成子问题 int mid = l + r >> 1; //递归处理子问题 merge_sort(q, l, mid); merge_sort(q, mid + 1, r); //合并子问题 int k = 0, i = l, j = mid + 1; while (i <= mid && j <= r) if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ]; else tmp[k ++ ] = q[j ++ ]; while (i <= mid) tmp[k ++ ] = q[i ++ ]; while (j <= r) tmp[k ++ ] = q[j ++ ]; for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j]; }
为什么不用 mid - 1 作为分隔线呢?
即 merge_sort(q, l, mid - 1 ), merge_sort(q, mid, r)
因为 mid = l + r >> 1 是向下取整，mid 有可能取到 l (数组只有两个数时)，造成无限划分
解决办法: mid 向上取整就可以了, 即 mid = l + r + 1 >> 1,如下所示:
void merge_sort(int q[], int l, int r) { if(l >= r) return; int mid = l + r + 1>> 1; merge_sort(q, l, mid - 1 ), merge_sort(q, mid, r); int k = 0, i = l, j = mid; while(i < mid && j <= r) if(q[i] <= q[j]) tmp[k++] = q[i++]; else tmp[k++] = q[j++]; while(i < mid) tmp[k++] = q[i++]; while(j <= r) tmp[k++] = q[j++]; for(k = 0, i = l; i <= r; k++, i++) q[i] = tmp[k]; }
归并排序
#include<iostream> using namespace std; #define N 100001 int a[N]; int tmp[N]; void merg_sort(int a[],int left,int right) { if(left>=right) { return ; } int mid=(left+right)>>1; merg_sort(a,left,mid); merg_sort(a,mid+1,right); int k=0,i=left,j=mid+1; while(i<=mid&&j<=right) { if(a[i]<a[j]) tmp[k++]=a[i++]; else tmp[k++]=a[j++]; } while(i<=mid) tmp[k++]=a[i++]; while(j<=right) tmp[k++]=a[j++]; for(int i=left,j=0;i<=right;i++,j++) { a[i]=tmp[j]; } } int main() { int n; scanf("%d",&n); for(int i=0;i<n;i++) { scanf("%d",&a[i]); } merg_sort(a,0,n-1); for(int i=0;i<n;i++) { printf("%d ",a[i]); } return 0; }
逆序对数量
#include<iostream> using namespace std; #define N 100001 int a[N]; int tmp[N]; typedef long long ll; ll res=0; void merg_sort(int a[],int left,int right) { if(left>=right) { return ; } int mid=(left+right)>>1; merg_sort(a,left,mid); merg_sort(a,mid+1,right); int k=0,i=left,j=mid+1; while(i<=mid&&j<=right) { if(a[i]<=a[j]) {tmp[k++]=a[i++]; } else{ //例如[3,4,1,2]中q[0]>q[2],则q[0],q[1]都与q[2]成逆序对,而q[mid]与q[i]有mid-i+1个数字，因此逆序对增加mid-i+1 tmp[k++]=a[j++]; res+=mid-i+1; } } while (i <= mid) { tmp[k++] = a[i++]; } while (j <= right) { tmp[k++] = a[j++]; } for (int i = left, j = 0; i <= right; i++, j++) { a[i] = tmp[j]; } } int main() { int m; scanf("%d",&m); for(int i=0;i<m;i++) { scanf("%d",&a[i]); } merg_sort(a,0,m-1); printf("%lld",res); return 0; }
