-
快速排序：
-
原理：找到一個基準數，小于它的放一邊，大于它的在另一邊
-
應用：排序，STL sort
-
模板：
void quicksort(int l,int r) { //取左一為基準軸 int i=l,j=r; int k=a[l]; if(i>=j) return; while(i<j) { while(i<j && a[j]>k) j--; if(i<j) {a[i]=a[j]; i++} while(i<j && a[i]<=k) i++; if(i<j) {a[j]=a[i]; j--} } a[i] = k; quicksort(l,i-1); quicksort(i+1,r); }優化：選取基準軸時采用三數取中法，磁區規模夠小時采用插排法，聚集相等元素，優化尾遞回等...
void qsort(int l,int r) { int mid=a[(l+r)/2]; int i=l,j=r; while(i<j) { while(a[i]<mid) i++; while(a[j]>mid) j--; if(i<=j) { swap(a[i],a[j]); i++; j--; } } if(l<j) qsort(l,j); if(i<r) qsort(i,r); }
-
-
歐拉篩法(線性篩)：
-
原理：最小質因數*最大因數(非自身) = 合數,如此每個數僅被洗掉一次（
沒明白,背模板就完事了） -
模板：
cnt = 0; memset(isPrime,1,sizeof(isPrime)); isPrime[1] = 0; for(int i=2; i<=n; i++) { if(isPrime[i]) Prime[++cnt] = i; for(int j=1; j<=cnt && i*Prime[j]<=n; j++) { isPrime[i*Prime[j]] = 0; if(i%Prime[j] == 0) break; } }
-
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/101265.html
標籤：其他