二分及快速排序

二分及排序CopyRight

by

CDD2017年11月28日二分查找【例6

.

10】找数。给一个长度为n的单调增的正整数序列，即序列中

每一个数都比前一个数大。有m个询问，每次询问一个x,问序列中最后

一个小于等于x的数是什么?输入格式：第1行，两个整数n,m;接下来一行n

个数，表示这个序列；接下来m行每行一个数，表示一个询问。输出格式：输出共m

行，表示序列中最后一个小于等于x

的数是什么。

写如没有，则输出-1。输入样例：5312346513输出样例：413二分查找分析：我们用Left

表示询问区间的左边界，用Right

表示询问区间的右边界，[Left,Right]组成询问区间。

一开始

Left=1,Right=n,序列已经按照升序排好，保证了二分的有序性。每一次二分，我们这样来做：(1)取区间中间值Mid=(Left+Right)/2。(

2

)

判

断a[Mid]

与x的关系，如果a[Mid]>x,由于序列是升序排列，所以区间[Mid,Right]都可以被排除，修改右边界Right=Mid-1。(

3

)

如

果a[Mid]<=x,修改左边界Left=Mid+1

。

重复执行二分操作直到Left>Right。下面我们来分析答案的情况，循环结束示意图如图6.19所示。图6.19

二分循环结束示意图最终循环结束时一定是Left=Right+1,根据二分第(2)步的做法我们

知道

Right

的右边一定都是大于x

的，而根据第(3)步我们可以知道Left

左

边一定是小于等于x的

。所以，

一

目了然，最终答案是Right

指向的数。Right=0就是题自中

输出-1的情况。//eg6.10#include<iostream>using

namespace

std;int

n,m,a[110000];int

main(){cin

>>n

>>m;for(inti=1;i<=n;i++)cin>>a[i];a[0]=-1;for(inti=1;i<=m;i++){int

X;intleft=1,right=n,mid;cin>>X;while(left<=right){mid=(left+right)/2;if(a[mid]<=X)left

=mid

+1;

else

right

=mid

-1;}cout<<a[right]<<endl;}return

0;}123456789101112131415161718192021222324程序eg6.10

如下：二分查找【例

6

.11】月度开销。农夫约翰是一个精明的会计师。

他意识到

自己可能没有足够的钱来维持农场的运转了。他计算出并记录下了接

下来

N(1≤N≤100,000)

天里每天需要的开销。约翰打算为连续的

M(1≤M≤N)个财政周期创建预算案，他把一个财政周期命名为fajo

月。

每个fajo

月包含一天或连续的多天，每天被恰好包含在一个fajo

月里。约

翰的目标是合理安排每个fajo

月包含的天数，使得开销最多的fajo月的开

销尽可能少。输人格式：第1行，包含两个整数N,M,用单个空格隔开；接下来N行，

每行包含一个1到10000之间的整数，按顺序给出接下来N天里每天的开销。输出格式：

一个整数，即最大月度开销的最小值。输入样例

：75100400300100500101400输出样例：500二分查找分析：不妨设ok(i)表示是否存在一种方案使得开销最多的fajo

月的开销小于等于i

。判断ok(i)可以用贪心法，从左到右扫描每一天的开销，

采用“物尽其用”原则，在不超过i

的前提下让每一个fajo

月的天数越多越好，如果最终得到的预算案小于等于M,则ok(i)=1,答案可以比i再小一些，如果大于M,则ok(i)=0,答案要比i大一些。这就满足了二分的有

序

性

。用L

表示二分区间左边界，R

表示右边界，当L<=R时：(1)Mid=(L+R)/2。(2)如果ok(Mid)=1,则R=Mid-1,

否则L=Mid+1。重复执行直到L>R,由

于L的左边都是小于答案的，R的右边是大于

等于答案的。所以最终答案就是L。程序如下：1//eg

6.112

#include

<iostream>3using

namespacestd;4constintMAXN=100005;5int

A[MAXN],N,M;6

boolok(intlimit)//判断limit对应的fajo月数是否不超过M7

{8intc=1;9

for(int

i=1,sum

=0;i<=N;i

++)10

if(sum

+A[i]<=limit)sum+=A[i];else11

{12

++C;13

sum

=A[i];14

if(sum>limit)return0;15

}16

return

c

<=M;17

}18

int

main()19

{20

cin

>>N

>>M;21

for(int

i=1;i<=N;i

++)cin

>>A[i];22

int

1=1,r=10000

*N;23

while(1<=r)24

{25

int

mid=1+r>>1;26

if(ok(mid))r=mid

-1;else1=mid+1;27

}28

cout<<1<<endl;29

return

0;30

}快速排序【例6

.

12】排序。给你一个长度为n的序列，让你给这个序列从小到

大排序。(n<=100000)输入格式：第1行，一个整数n;第2行n个整数，表示这个序列。输出格式：1行，

n

个整数，表示排序好的序列。输入样例：6245137输出样例：123457分析：

如果使用选择排序，时间复杂度为O(n²)

。对于本题来说不能在1秒内出解，超时。下面介绍快速排序。快速排序快速排序的基本思想是：通过一趟排序将待排记录分割成独立的左右两部分，其中左边的所有元素都比右边的元素要小，接下来分别对这两部

分继续进行排序，那么整个序列就有序了。当i<=j

时

，i从当前位置往右扫描找到第一个大于等于基准数的元素.j

从当前位置往左扫描找到第一个小于等于基准数的元素，如果i<=j,交换a[i]与

a[j],交换完后a[i]小于等于基准数，指针i

向右移动

一位，a[i

大于等于基准数，指针j向左移动一位。重复执行以上操作直到i>j为止。以上划分把原序列划分成三部分：(1)左边{A[L],A[L+1],…,A[j]}:这一部分的元素小于等于基准数T(2)中间{A[j+1],A[j+2],…,A[i-1]}:这一部分的元素等于基准数T(3)右边{A[i],A[i+1],…,A[R]}:这一部分的元素大于等于基准数T

接下来对左边和右边进行递归处理即可。快速排序(4)基准数不能选择第一个或者中间的位置固定的数，这样的程序

有把程序卡得很慢的针对性的数据，建议用上面程序中随机产生基准数：

较

好

。第一遍84838887615070608099//将当前序列在中间位置的数定义为分隔数//在左半部分寻找比中间数大的数//在右半部分寻找比中间数小的数//若找到一组与排序目标不一致的数对则交换它们//继续找//注意这里不能有等号//若未到两个数的边界，

则递归搜索左右区间int

i,j,mid,p;i=l;

j=r;mid=a[(l+r)/2];dowhile

(a[i]<mid)i++;while

(a[j]>mid)j--

;if(i<=j)p=a[i];if(i<r)

qso

rt(i,r);基准只是一个比较数字，可以随机使用，它在排序中也共同参与排序，没有特殊

化。参考程序代码1

快速排序算法2

void

qsort(int

l,int

r)a[i]=a[j];a[j]=p;i++;

j--;4程序eg6.12如下：1

//eg

6.122#include

<iostream>3#include

<algorithm>4#include

<ctime>5#include

<cstdlib>6

using

nanespace

std;7const

int

MAXN

=100005;8int

A[MAXN],N;9void

qsort(int

L,int

R)10

{11

if(L>=R)return;12int

i=L,j=R,T=A[rand()%(R-L+1)+L];13while(i<=j)14{15

while(A[i]<T)i++;16

while(A[j]>T)j--;17

if(i<=j)18{19

swap(A[i],A[j]);20

i++;21

j--;22

}23

}24

qsort(L,j);25qsort(i,R);

26}27

int

main()28{29

cin>>N;30for(inti=1;i<=N;i++)cin>>A[i];31srand(int(time(0)));32

qsort(1,N);33

for(inti=1;i<=N;i++)cout<<A[i]<<”“;34

cout<<endl;35return

0;36

}//快速排序合

并418

32834610

2578234567810合并过程为：比较a[i]和a[j]的大小，若a[i]≤a[j],

则将第一个有序表中的元素

a[i]复制到r[k]中，并令i和k分别加上1;否则将第二个有序表中的元素a[j]复制到r[k]

中，并令j和k分别加上1,如此循环下去，直到其中一个有序表取完，然后再将另一个有

序表中剩余的元素复制到r中从下标k到下标t的单元。归并排序的算法我们通常用递归实

现，先把待排序区间[s,t]以中点二分，接着把左边子区间排序，再把右边子区间排序，最后把左区间和右区间用一次归并操作合并成有序的区间[s,t]。归并排序归并排序是建立在归并操作上的一种有效的排序算法，该算法是采用分治法(Divide

and

Conquer)的一个非常典型的应用。将已有序的子序列合并，得到完全有序

的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序

表，称为二路归并。例如有8个数据需要排序：104638257归并排序主要分两大步：分解、合并。10463825

7104638257104828分

解归并排序动态图示6

5

3

1

8

7

2

4【程序实现】void

msort(int

s,int

t){if(s==t)return;//如果只有一个数字则返回，无须排序int

mid=(s+t)/2;msort(s,mid);

//分解左序列msort(mid+1,t);

//分解右序列int

i=s,j=mid+1,k=s;

//

接下来合并while(i<=mid&&j<=t){if(a[i]<=a[j]){r[k]=a[i];k++;i++;}else{r[k]=a[j];k++;j++; while(i<=mid)