1：快速排序
先上模板
// 快速排序算法模板
void quick_sort(int q[], int l, int r)
{
if (l >= r) return;
int i = l - 1, j = r + 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]);
else break;
}
quick_sort(q, l, j), quick_sort(q, j + 1, r);
}
然后是習(xí)題
快速排序的基本思想是基于分治
大致思想是
假設(shè)我們有一個集合q 左端點(diǎn)為l,右端點(diǎn)為r
我們現(xiàn)在集合確認(rèn)一個分界點(diǎn) m纷铣，m的常用取值有q[l],q[r],q[(l+r)/2] 或者區(qū)間內(nèi)任意一個點(diǎn)都行
然后我們要做的就是 調(diào)整這個區(qū)間卵史，使的區(qū)間的左側(cè)ql[]都<=m區(qū)間的右側(cè)qr[]都>=m
這樣我們就對區(qū)間進(jìn)行了一個初步的整理
然后我們要做的就是遞歸的去對 ql[],qr[]執(zhí)行上述步驟 直到細(xì)分后的區(qū)間元素?cái)?shù)量為1
所以快速排序的步驟就是：
1確定分界點(diǎn) (常用的點(diǎn)有q[l] , q[r] , q[(l+r)/2])
2調(diào)整區(qū)間 使得左側(cè)區(qū)間的值都小于等于m右側(cè)區(qū)間的值都大于等于m
3遞歸處理左右兩端
然后我們會發(fā)現(xiàn) 其中比較復(fù)雜的就是第二部 對區(qū)間進(jìn)行處理
我們可以先講一種邏輯上比較簡單 比較暴力的做法：
我們可以新開兩個數(shù)組用于存放所有<=m的值和所有>m的值
然后我們再將這兩個數(shù)組中的值填入原數(shù)組
但這樣我們需要一個額外的空間 而且做法比較暴力這里我們有一個比較巧妙的方法去解決這個問題
我們可以定義兩個指針 i,j來對整個區(qū)間進(jìn)行掃描 這里我們?nèi)?strong>m=q[l]=2
首先我們來看i指針指向的元素2 不滿足q[i]<m(2) 因此指針i先停下來然后我們在依次看j指向的數(shù)5>2成立，2>2 不成立此時j也停下 此時 j>i 交換q[i]與q[j]
此時結(jié)果如下
然后我們繼續(xù)
i指向1搜立，1<2成立 i繼續(xù)移動
i指向3以躯，3<2不成立 i停止移動 j開始移動
j指向3，3>2成立啄踊，j繼續(xù)移動
j指向1忧设，1>2不成立 j停止運(yùn)動
此時i=2,j=1 i>j 說名到這里我們已經(jīng)掃描完成一遍元素了，并得到以下結(jié)果
由于i>j 所以我們可以保證在(l,j)區(qū)間內(nèi)颠通，所有的元素都被i指針掃描過一次 故所有的元素都小于等于m址晕，同理在(j+1,r)中，左右的元素值都大于等于m
這樣便完成了一次對數(shù)組的整理
之后我們分別對( l , j )和( j+1 , r )兩個區(qū)間進(jìn)行處理即可
然后我們來最開始習(xí)題的題解
#include<iostream>
using namespace std;
const int N=1e6+10;
int nums[N];
void QuickSort(int q[],int l,int r)
{
if(l>=r)
return;
int mid=q[l],i=l-1,j=r+1;
while(i<j)
{
do i++; while(q[i]<mid);
do j--; while(q[j]>mid);
if(i<j)
swap(q[i],q[j]);
}
QuickSort(q,l,j);
QuickSort(q,j+1,r);
}
int main()
{
int count;
scanf("%d",&count);
for(int i=0;i<count;i++)
scanf("%d",&nums[i]);
QuickSort(nums,0,count-1);
for(int i=0;i<count;i++)
printf("%d ",nums[i]);
return 0;
}
快速排序練習(xí)題：第K個數(shù)
給定一個長度為n的整數(shù)數(shù)列顿锰，以及一個整數(shù)k谨垃，請用快速選擇算法求出數(shù)列的第k小的數(shù)是多少启搂。
輸入格式
第一行包含兩個整數(shù) n 和 k。
第二行包含 n 個整數(shù)（所有整數(shù)均在1~109范圍內(nèi)）刘陶，表示整數(shù)數(shù)列胳赌。
輸出格式
輸出一個整數(shù)，表示數(shù)列的第k小數(shù)匙隔。
數(shù)據(jù)范圍
1≤n≤100000,
1≤k≤n
輸入樣例：
5 3
2 4 1 5 3
輸出樣例：
3
先來分析一下這道題
給的是一個無序的數(shù)組疑苫，找到第k個數(shù) 首先想到的就是 先把整個數(shù)組 快排 然后輸出低K個數(shù)
但這樣其實(shí)我們相當(dāng)于進(jìn)行了很多多余的操作
// 快速排序算法模板
void quick_sort(int q[], int l, int r)
{
if (l >= r) return;
int i = l - 1, j = r + 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]);
else break;
}
quick_sort(q, l, j), quick_sort(q, j + 1, r);
}
我們來看這個模板 每進(jìn)行一次排序，他需要對左右兩邊都進(jìn)行一次排序的操作纷责。然而我們需要找到第K個數(shù)捍掺，所以我們只需要去對有第K個數(shù)的范圍進(jìn)行排序即可
例如 我們第一次排序后 將數(shù)組以j為邊界分為了左右兩側(cè)，此時各個數(shù)據(jù)的值為
i=0 j=5 r=10 k=7再膳，左側(cè)的元素?cái)?shù)量nl=j-1+1=6 小于k
那么我們只需要對 (j+1,r)范圍內(nèi)查找第k個 因?yàn)樽髠?cè)的所有元素均小于等于右側(cè)的所有元素
那么相當(dāng)于 我們在左側(cè)已經(jīng)找過nl個數(shù)了 所以相當(dāng)于在右側(cè)查找 第 k-nl位元素 所以如果k在左側(cè)區(qū)域挺勿，不需要跟新k， k在右側(cè)區(qū)域內(nèi) 對k進(jìn)行更新
所以有
if(j-l+1>=k)
return QuickFind(q,l,j,k);
else
{
k-=(j-l+1);
return QuickFind(q,j+1,r,k);
}
而因?yàn)槲覀兠恳淮沃粚? 存在k的一側(cè)進(jìn)行更新查找饵史，所以當(dāng)遇到 l>=r時满钟，這個值就是我們要查找的元素
下面是題解
#include<iostream>
using namespace std;
const int N=1e6+10;
int nums[N];
int QuickFind(int q[],int l,int r,int k)
{
if(l>=r)
return q[l];
int mid=q[l],i=l-1,j=r+1;
while(i<j)
{
do i++; while(q[i]<mid);
do j--; while(q[j]>mid);
if(i<j)
swap(q[i],q[j]);
}
if(j-l+1>=k)
return QuickFind(q,l,j,k);
else
{
k-=(j-l+1);
return QuickFind(q,j+1,r,k);
}
}
int main()
{
int n,k;
scanf("%d%d",&n,&k);
for(int i=0;i<n;i++)
scanf("%d",&nums[i]);
int res= QuickFind(nums,0,n-1,k);
printf("%d",res);
}
2：歸并排序
先上算法模板
// 歸并排序算法模板
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];
}
歸并排序的思想也是基于分治 但和快速排序不同的是，歸并排序是一種穩(wěn)定的排序算法 而且歸并排序的時間復(fù)雜度無論任何情況都是 n(logn) 而快速排序的平均時間復(fù)雜度為n(logn) 最壞情況下為 n^2
(關(guān)于排序算法是不是穩(wěn)定 指的是： 當(dāng)一個排序過程中有兩個相等的元素時 排序結(jié)束后如果兩個元素的前后關(guān)系可能會發(fā)生變化那么就是 不穩(wěn)定的 而如果不會變化就是穩(wěn)定的 快速排序就是一種不穩(wěn)定算法 當(dāng)然我們也可以通過操作來將不穩(wěn)定算法變?yōu)榉€(wěn)定算法 例如快速排序胳喷，我們可以在只對值排序的基礎(chǔ)上增加上下標(biāo)湃番， 變成pair<值，下標(biāo)> 對pair來進(jìn)行排序 這樣我們就可以保證里面所有的值都是唯一的)
歸并排序的思想為 以下三部
- 每次講待排序的數(shù)組從中間分為左右兩個數(shù)組
- 將兩個數(shù)組分別排序
- 將兩個有序的數(shù)組合二為一
我們可以發(fā)現(xiàn)吭露，步驟中比較復(fù)雜的為第三部 合二為一 這里我們可以使用雙指針?biāo)惴?過程如下
開始時先創(chuàng)鍵 i 和 j兩個指針
然后在過程中我們用這兩個指針對數(shù)組進(jìn)行掃描吠撮，判斷
若 a[i]<=b[j] 我們便將a[i]存入，并將i++
若 a[i]>b[j] 我們便將b[j]存入讲竿，并將j++
當(dāng) i 或者 j 掃描到末尾時泥兰，我們停止掃描。
此時我們再看
若 i<a.lengh 說名a中有元素沒有全部放入有序數(shù)組中题禀，我們將a中的剩余元素放入
若 j<b.lengh 說名b中有元素沒有全部放入有序數(shù)組中鞋诗，我們將b中的剩余元素放入
在排序中我們需要開辟一個新的臨時數(shù)組temp來存放合并后的數(shù)組，在合并完成后我們 temp中的數(shù)據(jù)放回原數(shù)組當(dāng)中
來看一道習(xí)題 787. 歸并排序
給定你一個長度為n的整數(shù)數(shù)列迈嘹。
請你使用歸并排序?qū)@個數(shù)列按照從小到大進(jìn)行排序削彬。
并將排好序的數(shù)列按順序輸出。
輸入格式
輸入共兩行秀仲，第一行包含整數(shù) n融痛。
第二行包含 n 個整數(shù)（所有整數(shù)均在1~109范圍內(nèi)），表示整個數(shù)列神僵。
輸出格式
輸出共一行雁刷，包含 n 個整數(shù)，表示排好序的數(shù)列保礼。
數(shù)據(jù)范圍
1≤n≤100000
輸入樣例：
5
3 1 2 4 5
輸出樣例：
1 2 3 4 5
思路上面都講過了下面直接上代碼
#include<iostream>
using namespace std;
const int N=1e6+10;
int q[N],temp[N];
void MergeSort(int q[],int l, int r)
{
if(l>=r)
return;
int mid=l+r>>1;
MergeSort(q,l,mid);
MergeSort(q,mid+1,r);
int i=l,j=mid+1,k=0;
while(i<=mid && j<=r)
{
if(q[i]<=q[j])
temp[k++]=q[i++];
else
temp[k++]=q[j++];
}
while(i<=mid) temp[k++]=q[i++];
while(j<=r) temp[k++]=q[j++];
for(int i=l,j=0;i<=r;i++,j++)
{
q[i]=temp[j];
}
}
int main()
{
int n;
scanf("%d",&n);
for(int i=0;i<n;i++)
{
scanf("%d",&q[i]);
}
MergeSort(q,0,n-1);
for(int i = 0;i < n;i++)
{
printf("%d ",q[i]);
}
return 0;
}
第二道習(xí)題 788. 逆序?qū)Φ臄?shù)量
給定一個長度為n的整數(shù)數(shù)列沛励，請你計(jì)算數(shù)列中的逆序?qū)Φ臄?shù)量责语。
逆序?qū)Φ亩x如下：對于數(shù)列的第 i 個和第 j 個元素，如果滿 i < j 且 a[i] > a[j]侯勉，則其為一個逆序?qū)︷谐铮环駝t不是铝阐。
輸入格式
第一行包含整數(shù)n址貌，表示數(shù)列的長度。
第二行包含 n 個整數(shù)徘键，表示整個數(shù)列练对。
輸出格式
輸出一個整數(shù)，表示逆序?qū)Φ膫€數(shù)吹害。
數(shù)據(jù)范圍
1≤n≤100000
輸入樣例：
6
2 3 4 5 6 1
輸出樣例：
5
題解：
這道題直接一看很麻煩其實(shí)只需要按照上面歸并排序中的一步 當(dāng)我們每次發(fā)現(xiàn) a[i]>b[j]時
說名[a[i]),a[mid]]中所有元素均大于b[j] 所以 每次講b數(shù)組中的元素放入時螟凭，我們就相當(dāng)于找到了mid-i+1 個逆序?qū)?/p>
上代碼
#include<iostream>
using namespace std;
const int N=1e6+10;
int q[N],temp[N];
long long cnt;
void MergeSort(int q[],int l,int r)
{
if(l>=r)
return;
int mid=l+r>>1;
MergeSort(q,l,mid);
MergeSort(q,mid+1,r);
int k=0,i=l,j=mid+1;
while(i <= mid && j <= r)
{
if(q[i] <= q[j])
temp[k++]=q[i++];
else
{
cnt+=(mid-i+1);
temp[k++]=q[j++];
}
}
while(i <= mid) temp[k++]=q[i++];
while(j <= r) temp[k++]=q[j++];
for(int i=l,j=0;i<=r;i++,j++)
q[i]=temp[j];
}
int main()
{
int n;
scanf("%d",&n);
for(int i=0;i<n;i++)
scanf("%d",&q[i]);
MergeSort(q,0,n-1);
cout<<cnt;
}
2：二分
二分在整出查找里面是一種接近萬能的算法 并且對應(yīng)兩個模板
一個是區(qū)間為[l,mid][mid+1,r] 一個是[l,mid-1],[mid,r]
這里之前有一個詳細(xì)的帖子對二分進(jìn)行整理就不多贅述了 二分講解
直接來看習(xí)題
789. 數(shù)的范圍
給定一個按照升序排列的長度為n的整數(shù)數(shù)組，以及 q 個查詢它呀。
對于每個查詢螺男，返回一個元素k的起始位置和終止位置（位置從0開始計(jì)數(shù)）。
如果數(shù)組中不存在該元素纵穿，則返回“-1 -1”下隧。
輸入格式
第一行包含整數(shù)n和q，表示數(shù)組長度和詢問個數(shù)谓媒。
第二行包含n個整數(shù)（均在1~10000范圍內(nèi)）淆院，表示完整數(shù)組。
接下來q行句惯，每行包含一個整數(shù)k土辩，表示一個詢問元素。
輸出格式
共q行抢野，每行包含兩個整數(shù)拷淘，表示所求元素的起始位置和終止位置。
如果數(shù)組中不存在該元素指孤，則返回“-1 -1”启涯。
數(shù)據(jù)范圍
1≤n≤100000
1≤q≤10000
1≤k≤10000
輸入樣例：
6 3
1 2 2 3 3 4
3
4
5
輸出樣例：
3 4
5 5
-1 -1
#include<iostream>
using namespace std;
const int N=1e6+10;
int a[N];
int FindUp(int q[],int tar,int n)
{
int res=-1;
int l=0,r=n-1;
while(l<r)
{
int mid=l+r>>1;
if(q[mid]>=tar)
{
r=mid;
}
else
{
l=mid+1;
}
}
if(q[l]==tar)
res=l;
return res;
}
int FindDown(int q[],int tar,int n)
{
int res=-1;
int l=0,r=n-1;
while(l<r)
{
int mid=l+r+1>>1;
if(q[mid]<=tar)
{
l=mid;
}
else
{
r=mid-1;
}
}
if(q[l]==tar)
res=l;
return res;
}
int main()
{
int n,q;
scanf("%d%d",&n,&q);
for(int i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
for(int i=0;i<q;i++)
{
int tar;
scanf("%d",&tar);
int res=FindUp(a,tar,n);
if(res==-1)
cout<<"-1 -1"<<endl;
else
cout<<res<<" "<<FindDown(a,tar,n)<<endl;
}
}
直接上代碼
題目要求是求給定有序數(shù)組里面數(shù)出現(xiàn)的范圍，而我們二二分模板兩個剛好是查找 最左端和最右端 所以直接用兩個二分分別找到左端和右端的地址輸出即可
浮點(diǎn)數(shù)二分
先上題目790. 數(shù)的三次方根
給定一個浮點(diǎn)數(shù)n邓厕，求它的三次方根逝嚎。
輸入格式
共一行，包含一個浮點(diǎn)數(shù)n详恼。
輸出格式
共一行补君，包含一個浮點(diǎn)數(shù)，表示問題的解昧互。
注意挽铁，結(jié)果保留6位小數(shù)伟桅。
數(shù)據(jù)范圍
?10000≤n≤10000
輸入樣例：
1000.00
輸出樣例：
10.000000
浮點(diǎn)數(shù)二分的過程就是 我們先根據(jù)題意找到合適的 l r
例如這道題，數(shù)據(jù)范圍是-10000~10000
我們可以先大概對左右兩個端點(diǎn)的三次方根秋一下
303030=9000 404040=16000
所以我們可以把 l 和 r 定為-40和40
然后我們再看輸出格式 要求保留小數(shù)點(diǎn)后六位
一般情況下 最好多計(jì)算兩位保證精度不會缺失
然后上代碼
#include<iostream>
using namespace std;
int main()
{
double i=-100,j=100;
double n;
cin>>n;
while(j-i>1e-8)
{
double mid=(i+j)/2;
if(mid*mid*mid<n)
{
i=mid;
}
else
j=mid;
}
printf("%.6f",i);
}
