AcWing基礎講座の学習
ソート
1. クイックソート
1. 原理
無秩序な数列を並べ替えるには、以下の手順で進めることができる：
- 一段の数列に対して、まず任意の点を
midとして判定点とする。（このmidは一般に数列の中央の要素である） - この数列を一度走査し、
midより大きい数は右端へ、midより小さい数は左端へ置く。 - その後、分割された列について、
[l,p]、[p+1,r]の2つのサブ区間を選び、上記の操作を続け、長さが1になるまで繰り返す。（pは前述の左右の端の境界点）
2. 具体的な実装（コード)
本コードの考え方はy総を参考にした
void quick_sort(int a[],int l,int r){ if(l>=r) return;//设置退出条件 int i=l-1,j+1,mid = a[l+r>>1];//设置判断点 while(i<j){ do i++;while(a[i]<mid); do j--;while(a[j]>mid); if(i<j) swap(a[i],a[j]); } quick_sort(a,l,j);//继续对子段排序 quick_sort(a,j+1,r);}- 計算量：O(N*logN)
3. 関連問題
2. マージソート
1. 原理
無秩序な数列について、クイックソートと同様、これを並べ替えるには次の手順で進める：
- 一段の数列に対して、まず任意の点を
midとして分割点とする。（このmidは一般に数列の中点である） - その後、
[l,mid]、[mid+1,r]の2つのサブ区間を選択して並べ替えを続け、すでに整列済みと仮定する。 - その後、すでに整列済みの2つの区間を、整列順に先に
b配列へ格納し、次に整列済みの数列で元の数列を上書きする。
2. 具体的な実装（コード)
本コードの考え方はy総を参考にした
void merge_sort(int a[],int b[],int l,int r){ if(l>=r) return;//设置退出条件 int mid = l+r>>1,i=l,j=mid+1,k=0;//设置分割点 merge_sort(a,b,l,mid);merge_sort(a,b,mid+1,r);//先对子段排序 while(i<=mid&&j<=r) if(a[i]<=a[j]) b[k++] = a[i++]; else b[k++] = a[j++]; while(i<=mid) b[k++]=a[i++]; while(j<=r) b[k++]=a[j++]; for(i=l,j=0;i<=r;i++,j++) a[i]=b[j];}- 計算量：O(N*logN)
3. 関連アプリケーション
- 逆順対
マージソートで配列を並べ替える際、a[i]>b[j] が現れた時、それは逆順対が現れたことを意味し、かつ現在のa[j]については、mid - i + 1 個の逆順対が現れる。すなわちa[j]と[i, mid]が合計でmid - i + 1個の数の組み合わせとなって逆順対を成す。これにより、並べ替え時に対応する配列に存在する逆順対を求めることができる。
long long merge_sort(int a[],int b[],int l,int r){ if(l>=r) return 0; int mid = l+r>>1,i=l,j=mid+1,k=0; long long ans = merge_sort(a,b,l,mid)+merge_sort(a,b,mid+1,r); while(i<=mid&&j<=r) if(a[i]<=a[j]) b[k++] = a[i++]; else ans += mid-i+1,b[k++]=a[j++]; while(i<=mid) b[k++] = a[i++]; while(j<=r) b[k++] = a[j++]; for(i=l,j=0;i<=r;i++,j++) a[i]=b[j]; return ans;}4. 関連問題
二分法
1. 整数二分探索
1.1 アルゴリズムの原理
単調な列について、その単調性を利用して、探している数kを以下の方法で見つけることができる：
まず探索範囲lとrを決定し、l<r の場合、範囲の中点midを取り、区間[l,r]を [l,mid] と [mid+1,r]（このとき mid = l+r>>1）または [l,mid-1] と [mid,r]（このとき mid = l+r+1>>1）に分け、l<r の条件の下で check(mid) 関数に基づき、lとrを更新し、l>=r になるまで続ける。
1.2 コード実装
本コードの考え方はy総を参考にした
//将区间[l,r]分为[l,mid]和[mid+1,r]int bsearch_1(int l,int r){ while(l<r){ int mid = l+r>>1; if(check(mid)) r=mid; else l=mid+1; }return l;}//将区间[l,r]分为[l,mid-1]和[mid,r]int bsearch_2(int l,int r){ while(l<r){ int mid = l+r+1>>1; if(check(mid)) l=mid; else r=mid-1 }}1.3 相关题目
2. 浮点数二分
2.1 アルゴリズムの原理
単調な列について、その単調性を活用して、整数の二分探索と同様に、探している数kを見つけることができる：
まず探索範囲lとrを決定し、r-l>eps のとき、範囲の中点midを取り、mid=(l+r)/2、次に r-l>eps の条件の下で check(mid) 関数に基づき、lとrを更新し、r-l<=eps になるまで続ける
2.2 コード実装
本コードの考え方はy総を参考にした
double bsearch(double l,double r){ while(r-l>eps){ double mid = (l+r)/2; if(check(mid)) r=mid; else l=mid; }return l;}2.3 関連題目
この記事が役に立ったときは、ぜひ他の人に共有してください!
一部の情報は古い可能性があります