大家好，我是讯享网，很高兴认识大家。

目录

 

一、快速排序

1.零散知识点

（1）swap（）函数：

（2）>>位运算

（3）const int N=1e6+10；             

2.快速排序模板题

（1）AcWing 785 快速排序

3.时间复杂度：

 二、归并排序

1.零散知识点

（1）稳定排序和不稳定排序

2.归并排序模板题

3.时间复杂度： 

三、二分查找（整数）

1.核心思路图示

​ 2.二分查找模板题

3.时间复杂度

四、二分查找（浮点数）

1.核心思路图示

 2.求平方根模板

---

一、快速排序

1.零散知识点

（1）swap（）函数：

C++标准库函数，可以交换两个变量的值。包括：整数，字符串，数组，以及栈等数组结构。

 swap函数详细解释

c++内置了swap函数,头文件#include<iostream>,如果自己重新手写swap函数可能会与原本的内置的函数产生冲突，所以可以将函数名改为Swap或swap1。

（2）>>位运算

i=x+y>>1; //这个是（x+y）的二进制值所有位向右移动一位，即除以2。 i = i << 2; //把i里的值左移2位

讯享网

      左移里一个比较特殊的情况是当左移的位数超过该数值类型的最大位数时,编译器会用左移的位数去模类型的最大位数,然后按余数进行移位,如:

　　int i = 1, j = 0x;           //设int为32位

　　i = i << 33;                                 // 33 % 32 = 1 左移1位,i变成2

　　j = j << 33;                                 // 33 % 32 = 1 左移1位,j变成0,最高位被丢弃

位运算优先级：

讯享网

（3）const int N=1e6+10；             

//1*10^6+10

2.快速排序模板题

（1）AcWing 785 快速排序

给定你一个长度为 n 的整数数列。

请你使用快速排序对这个数列按照从小到大进行排序。

并将排好序的数列按顺序输出。

输入格式

输入共两行，第一行包含整数 n。

第二行包含 n 个整数（所有整数均在 1∼1091∼109 范围内），表示整个数列。

输出格式

输出共一行，包含 n 个整数，表示排好序的数列。

数据范围

1≤n≤

输入样例：

讯享网5 3 1 2 4 5 

输出样例：

1 2 3 4 5

第一次的代码，跟y总的一样，取第一个元素作为分割点，但是不能ac 。应该把其中的int x=p[l]换成int x=p[(l+r)>>1]，因为给出的案例中，大部分元素都是正序排列，swap函数执行的次数可以忽略不计。如果取第一个元素的话，之后的大多数元素都比第一个元素大，所以 i 指针（从左向右移动的那个），几乎每移动一次都要停下来，进行元素交换，swap函数的执行次数接近n/2。

讯享网#include<iostream> #include<stdio.h> using namespace std; const int N=1e6+10; void quick_sort(int p[],int l,int r){ if(l>=r) return;//先排除元素个数1和0的情况，第一次忘写了 int x=p[l],i=l-1,j=r+1;//这个地方把int x=p[l]换成int x=p[(l+r)>>1]才能ac，对于这个题目的案例时间复杂度更小 while(i<j){//这里注意指针i在指针j左边的时候继续循环 do i++;while (p[i]<x); do j--;while (p[j]>x);//这里记得是j--，错三次了 if(i<j) swap(p[i],p[j]);//假如指针i>j，此时指针j所指位置及其左边已经符合条件 //指针i所指位置及其右边也符合条件，所以不需要再作调换 } //分成前后两部分，然后不断递归，直至所有元素按顺序排列 quick_sort(p,l,j); quick_sort(p,j+1,r); } int main (){ int n; int p[N]; scanf("%d",&n); //输入数组 for(int i=0;i<n;i++) scanf("%d",&p[i]); quick_sort(p,0,n-1); //输出数组 for(int i=0;i<n;i++) printf("%d ",p[i]); }

需要注意的是，上面快速排序算法核心步骤中，int x = p[l]对应下面的quick_sort(p,l,j)和quick_sort(p,j+1,r)，此时x不能取数组右边界；而int x = p[r]对应的是quick_sort(p,l,i-1)和quick_sort(p,i,r),此时x不能取数组左边界，否则当i=0时，左边为空集，右边为原区间。

下面这个案例通过不了

 15915 16204 16772 39929 49780 54646 77889 95421 99907                                                                                                                                                                                                                                                              25...

3.时间复杂度：

最坏情况：O(N2)

最好情况和平均情况：O(NlogN)

 

---

 二、归并排序

1.零散知识点

（1）稳定排序和不稳定排序

归并排序是稳定的，而快速排序是不稳定的。通俗地讲就是能保证排序前两个相等的数其在序列的前后位置顺序和排序后它们两个的前后位置顺序相同。

• 稳定排序：冒泡、插入、归并
• 不稳定排序：选择、希尔、快速排序(可以做到稳定但是比较难)、堆排序

快速排序不稳定的例子：3(1)  3(2)  1  4  5  -->  1  3(2)  3(1)  4  5                  //（1）（2）用来标记

让快速排序变成稳定的方法：就是快排中的所有元素各不相同。

2.归并排序模板题

给定你一个长度为 n的整数数列。

请你使用归并排序对这个数列按照从小到大进行排序。

并将排好序的数列按顺序输出。

输入格式

输入共两行，第一行包含整数 n。

第二行包含 n 个整数（所有整数均在 1∼1091∼109 范围内），表示整个数列。

输出格式

输出共一行，包含 n 个整数，表示排好序的数列。

数据范围

1≤n≤

输入样例：

讯享网5 3 1 2 4 5 

输出样例：

1 2 3 4 5

讯享网#include<iostream> using namespace std; const int N=1e6+10; int p[N],tmp[N]; void merge_sort (int p[],int l,int r){ if(l>=r) return; int mid=l+r>>1; merge_sort(p,l,mid),merge_sort(p,mid+1,r); int i=l,j=mid+1,k=0;//这一行语句也可以放在递归之前，结果不影响 while(i<=mid&&j<=r) if(p[i]<=p[j]) tmp[k++]=p[i++]; else tmp[k++]=p[j++]; //第一次写忘了，如果其中一个数组已经遍历结束，那只需要把另一个数组依次存入即可 while(i<=mid) tmp[k++]=p[i++]; while(j<=r) tmp[k++]=p[j++]; for(i=l,j=0;i<=r;i++,j++) p[i]=tmp[j]; } int main(){ int n; scanf("%d",&n); for(int i=0;i<n;i++) scanf("%d",&p[i]); merge_sort(p,0,n-1); for(int i=0;i<n;i++) printf("%d ",p[i]);//提交的时候要加空格，否则格式不对 }

3.时间复杂度： 

O(NlogN)              //分析过程跟快速排序类似

三、二分查找（整数）

1.核心思路图示

 2.二分查找模板题

给定一个按照升序排列的长度为 n的整数数组，以及 q 个查询。

对于每个查询，返回一个元素 k 的起始位置和终止位置（位置从 0 开始计数）。

如果数组中不存在该元素，则返回 -1 -1。

输入格式

第一行包含整数 n 和 q，表示数组长度和询问个数。

第二行包含 n 个整数（均在 1∼10000 范围内），表示完整数组。

接下来 q 行，每行包含一个整数 k，表示一个询问元素。

输出格式

共 q 行，每行包含两个整数，表示所求元素的起始位置和终止位置。

如果数组中不存在该元素，则返回 -1 -1。

数据范围

1≤n≤
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;//只要大于等于1e6就行，此时恰好覆盖测试数据 int p[N]; int main(){ int n,m; scanf("%d%d",&n,&m);//m代表查询次数 for(int i=0;i<n;i++) scanf("%d",&p[i]); while(m--){ int x; scanf("%d",&x);//x为要查询的数字 int l=0,r=n-1; //先进行模板一的循环是因为该循环求出的是x第一次出现的位置（假设x存在） while(l<r){ int mid=l+r>>1;//这个要放在while循环里，因为每一次循环都会更新l和r的值，所以循环开始时，要更新mid的值 if(p[mid]>=x) r=mid; else l=mid+1; } if(p[l]!=x) cout<<"-1 -1"<<endl; else { cout<<l<<" "; int l=0,r=n-1; while(l<r){ int mid=l+r+1>>1;//l=mid时，即mid出现在区间左边时，要令mid=l+r+1>>1，防止出现死循环 if(p[mid]<=x) l=mid; else r=mid-1; } //如果进入else语句，说明x存在，所以接下来不需要判断p[l]是否等于x，只需要将l输出即可 cout<<l<<endl; } } return 0; }

3.时间复杂度

logN              //每次不论是否满足设置的性质，都会进行一次二分切割，n个数字切割成1个时，循环结束，需要切割次数为logN；进行第二次循环同理，总共次数为2logN。

四、二分查找（浮点数）

1.核心思路图示

求一个数的平方根最需要注意的就是当这个数小于1的情况！！！

当x>=1时，就让x作为二分的右边界，这样方便可以求值非常大的数的平方根，不会因为右边界数值不够而被限制；

当x<1时，就让1作为二分的右边界，这样不会因为x的平方根大于x（超出二分范围）而取不到该平方根。

 2.求平方根模板

讯享网#include<iostream> using namespace std; int main() { double x; cin>>x;//被开方数 double l=0,r=x; if(x<1) r=1;//这个语句至关重要！！！ while(r-l>1e-8){//这个数字要比题目要求的保留位数多2，才能满足精度条件 double mid=(l+r)/2;//浮点数能不能用这个double mid=l+r>>1 if(mid*mid>=x) r=mid; else l=mid; } printf("%lf",l);//精确到小数点后6位，所以对应前面的1e-8； // %lf--->double %f--->float return 0; }

至此，y总网课第一节听完

2021/11/5 22:59

-------------------------------------------------------------------------