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è)我們有一個(gè)集合q 左端點(diǎn)為l,右端點(diǎn)為r
我們現(xiàn)在集合確認(rèn)一個(gè)分界點(diǎn) m，m的常用取值有q[l],q[r],q[(l+r)/2] 或者區(qū)間內(nèi)任意一個(gè)點(diǎn)都行
然后我們要做的就是 調(diào)整這個(gè)區(qū)間，使的區(qū)間的左側(cè)ql[]都<=m區(qū)間的右側(cè)qr[]都>=m
這樣我們就對(duì)區(qū)間進(jìn)行了一個(gè)初步的整理
然后我們要做的就是遞歸的去對(duì) 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遞歸處理左右兩端
然后我們會(huì)發(fā)現(xiàn) 其中比較復(fù)雜的就是第二部 對(duì)區(qū)間進(jìn)行處理
我們可以先講一種邏輯上比較簡(jiǎn)單 比較暴力的做法：
我們可以新開(kāi)兩個(gè)數(shù)組用于存放所有<=m的值和所有>m的值
然后我們?cè)賹⑦@兩個(gè)數(shù)組中的值填入原數(shù)組
但這樣我們需要一個(gè)額外的空間 而且做法比較暴力這里我們有一個(gè)比較巧妙的方法去解決這個(gè)問(wèn)題
我們可以定義兩個(gè)指針 i,j來(lái)對(duì)整個(gè)區(qū)間進(jìn)行掃描 這里我們?nèi)?strong>m=q[l]=2
首先我們來(lái)看i指針指向的元素2 不滿(mǎn)足q[i]<m(2) 因此指針i先停下來(lái)然后我們?cè)谝来慰磈指向的數(shù)5>2成立，2>2 不成立此時(shí)j也停下 此時(shí) j>i 交換q[i]與q[j]
此時(shí)結(jié)果如下
然后我們繼續(xù)
i指向1，1<2成立 i繼續(xù)移動(dòng)
i指向3，3<2不成立 i停止移動(dòng) j開(kāi)始移動(dòng)
j指向3，3>2成立，j繼續(xù)移動(dòng)
j指向1，1>2不成立 j停止運(yùn)動(dòng)
此時(shí)i=2,j=1 i>j 說(shuō)名到這里我們已經(jīng)掃描完成一遍元素了，并得到以下結(jié)果
由于i>j 所以我們可以保證在(l,j)區(qū)間內(nèi)，所有的元素都被i指針掃描過(guò)一次 故所有的元素都小于等于m，同理在(j+1,r)中，左右的元素值都大于等于m
這樣便完成了一次對(duì)數(shù)組的整理
之后我們分別對(duì)( l , j )和( j+1 , r )兩個(gè)區(qū)間進(jìn)行處理即可
然后我們來(lái)最開(kāi)始習(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個(gè)數(shù)
給定一個(gè)長(zhǎng)度為n的整數(shù)數(shù)列，以及一個(gè)整數(shù)k，請(qǐng)用快速選擇算法求出數(shù)列的第k小的數(shù)是多少。
輸入格式
第一行包含兩個(gè)整數(shù) n 和 k。
第二行包含 n 個(gè)整數(shù)（所有整數(shù)均在1~109范圍內(nèi)），表示整數(shù)數(shù)列。
輸出格式
輸出一個(gè)整數(shù)，表示數(shù)列的第k小數(shù)。
數(shù)據(jù)范圍
1≤n≤100000,
1≤k≤n
輸入樣例：
5 3
2 4 1 5 3
輸出樣例：
3
先來(lái)分析一下這道題
給的是一個(gè)無(wú)序的數(shù)組，找到第k個(gè)數(shù) 首先想到的就是 先把整個(gè)數(shù)組 快排 然后輸出低K個(gè)數(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);
}
我們來(lái)看這個(gè)模板 每進(jìn)行一次排序，他需要對(duì)左右兩邊都進(jìn)行一次排序的操作。然而我們需要找到第K個(gè)數(shù)，所以我們只需要去對(duì)有第K個(gè)數(shù)的范圍進(jìn)行排序即可
例如 我們第一次排序后 將數(shù)組以j為邊界分為了左右兩側(cè)，此時(shí)各個(gè)數(shù)據(jù)的值為
i=0 j=5 r=10 k=7，左側(cè)的元素?cái)?shù)量nl=j-1+1=6 小于k
那么我們只需要對(duì) (j+1,r)范圍內(nèi)查找第k個(gè) 因?yàn)樽髠?cè)的所有元素均小于等于右側(cè)的所有元素
那么相當(dāng)于 我們?cè)谧髠?cè)已經(jīng)找過(guò)nl個(gè)數(shù)了 所以相當(dāng)于在右側(cè)查找 第 k-nl位元素 所以如果k在左側(cè)區(qū)域，不需要跟新k， k在右側(cè)區(qū)域內(nèi) 對(duì)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)槲覀兠恳淮沃粚?duì) 存在k的一側(cè)進(jìn)行更新查找，所以當(dāng)遇到 l>=r時(shí)，這個(gè)值就是我們要查找的元素
下面是題解
#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)定的排序算法 而且歸并排序的時(shí)間復(fù)雜度無(wú)論任何情況都是 n(logn) 而快速排序的平均時(shí)間復(fù)雜度為n(logn) 最壞情況下為 n^2
(關(guān)于排序算法是不是穩(wěn)定 指的是： 當(dāng)一個(gè)排序過(guò)程中有兩個(gè)相等的元素時(shí) 排序結(jié)束后如果兩個(gè)元素的前后關(guān)系可能會(huì)發(fā)生變化那么就是 不穩(wěn)定的 而如果不會(huì)變化就是穩(wěn)定的 快速排序就是一種不穩(wěn)定算法 當(dāng)然我們也可以通過(guò)操作來(lái)將不穩(wěn)定算法變?yōu)榉€(wěn)定算法 例如快速排序，我們可以在只對(duì)值排序的基礎(chǔ)上增加上下標(biāo)， 變成pair<值，下標(biāo)> 對(duì)pair來(lái)進(jìn)行排序 這樣我們就可以保證里面所有的值都是唯一的)
歸并排序的思想為 以下三部
- 每次講待排序的數(shù)組從中間分為左右兩個(gè)數(shù)組
- 將兩個(gè)數(shù)組分別排序
- 將兩個(gè)有序的數(shù)組合二為一
我們可以發(fā)現(xiàn)，步驟中比較復(fù)雜的為第三部 合二為一 這里我們可以使用雙指針?biāo)惴?過(guò)程如下
開(kāi)始時(shí)先創(chuàng)鍵 i 和 j兩個(gè)指針
然后在過(guò)程中我們用這兩個(gè)指針對(duì)數(shù)組進(jìn)行掃描，判斷
若 a[i]<=b[j] 我們便將a[i]存入，并將i++
若 a[i]>b[j] 我們便將b[j]存入，并將j++
當(dāng) i 或者 j 掃描到末尾時(shí)，我們停止掃描。
此時(shí)我們?cè)倏?br>
若 i<a.lengh 說(shuō)名a中有元素沒(méi)有全部放入有序數(shù)組中，我們將a中的剩余元素放入
若 j<b.lengh 說(shuō)名b中有元素沒(méi)有全部放入有序數(shù)組中，我們將b中的剩余元素放入
在排序中我們需要開(kāi)辟一個(gè)新的臨時(shí)數(shù)組temp來(lái)存放合并后的數(shù)組，在合并完成后我們 temp中的數(shù)據(jù)放回原數(shù)組當(dāng)中
來(lái)看一道習(xí)題 787. 歸并排序
給定你一個(gè)長(zhǎng)度為n的整數(shù)數(shù)列。
請(qǐng)你使用歸并排序?qū)@個(gè)數(shù)列按照從小到大進(jìn)行排序。
并將排好序的數(shù)列按順序輸出。
輸入格式
輸入共兩行，第一行包含整數(shù) n。
第二行包含 n 個(gè)整數(shù)（所有整數(shù)均在1~109范圍內(nèi)），表示整個(gè)數(shù)列。
輸出格式
輸出共一行，包含 n 個(gè)整數(shù)，表示排好序的數(shù)列。
數(shù)據(jù)范圍
1≤n≤100000
輸入樣例：
5
3 1 2 4 5
輸出樣例：
1 2 3 4 5
思路上面都講過(guò)了下面直接上代碼
#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ù)量
給定一個(gè)長(zhǎng)度為n的整數(shù)數(shù)列，請(qǐng)你計(jì)算數(shù)列中的逆序?qū)Φ臄?shù)量。
逆序?qū)Φ亩x如下：對(duì)于數(shù)列的第 i 個(gè)和第 j 個(gè)元素，如果滿(mǎn) i < j 且 a[i] > a[j]，則其為一個(gè)逆序?qū)?；否則不是。
輸入格式
第一行包含整數(shù)n，表示數(shù)列的長(zhǎng)度。
第二行包含 n 個(gè)整數(shù)，表示整個(gè)數(shù)列。
輸出格式
輸出一個(gè)整數(shù)，表示逆序?qū)Φ膫€(gè)數(shù)。
數(shù)據(jù)范圍
1≤n≤100000
輸入樣例：
6
2 3 4 5 6 1
輸出樣例：
5
題解：
這道題直接一看很麻煩其實(shí)只需要按照上面歸并排序中的一步 當(dāng)我們每次發(fā)現(xiàn) a[i]>b[j]時(shí)
說(shuō)名[a[i]),a[mid]]中所有元素均大于b[j] 所以 每次講b數(shù)組中的元素放入時(shí)，我們就相當(dāng)于找到了mid-i+1 個(gè)逆序?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：二分
二分在整出查找里面是一種接近萬(wàn)能的算法 并且對(duì)應(yīng)兩個(gè)模板
一個(gè)是區(qū)間為[l,mid][mid+1,r] 一個(gè)是[l,mid-1],[mid,r]
這里之前有一個(gè)詳細(xì)的帖子對(duì)二分進(jìn)行整理就不多贅述了 二分講解
直接來(lái)看習(xí)題
789. 數(shù)的范圍
給定一個(gè)按照升序排列的長(zhǎng)度為n的整數(shù)數(shù)組，以及 q 個(gè)查詢(xún)。
對(duì)于每個(gè)查詢(xún)，返回一個(gè)元素k的起始位置和終止位置（位置從0開(kāi)始計(jì)數(shù)）。
如果數(shù)組中不存在該元素，則返回“-1 -1”。
輸入格式
第一行包含整數(shù)n和q，表示數(shù)組長(zhǎng)度和詢(xún)問(wèn)個(gè)數(shù)。
第二行包含n個(gè)整數(shù)（均在1~10000范圍內(nèi)），表示完整數(shù)組。
接下來(lái)q行，每行包含一個(gè)整數(shù)k，表示一個(gè)詢(xún)問(wèn)元素。
輸出格式
共q行，每行包含兩個(gè)整數(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)的范圍，而我們二二分模板兩個(gè)剛好是查找 最左端和最右端 所以直接用兩個(gè)二分分別找到左端和右端的地址輸出即可
浮點(diǎn)數(shù)二分
先上題目790. 數(shù)的三次方根
給定一個(gè)浮點(diǎn)數(shù)n，求它的三次方根。
輸入格式
共一行，包含一個(gè)浮點(diǎn)數(shù)n。
輸出格式
共一行，包含一個(gè)浮點(diǎn)數(shù)，表示問(wèn)題的解。
注意，結(jié)果保留6位小數(shù)。
數(shù)據(jù)范圍
?10000≤n≤10000
輸入樣例：
1000.00
輸出樣例：
10.000000
浮點(diǎn)數(shù)二分的過(guò)程就是 我們先根據(jù)題意找到合適的 l r
例如這道題，數(shù)據(jù)范圍是-10000~10000
我們可以先大概對(duì)左右兩個(gè)端點(diǎn)的三次方根秋一下
303030=9000 404040=16000
所以我們可以把 l 和 r 定為-40和40
然后我們?cè)倏摧敵龈袷?要求保留小數(shù)點(diǎn)后六位
一般情況下 最好多計(jì)算兩位保證精度不會(huì)缺失
然后上代碼
#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);
}
