一、快速排序

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 = 0x80000000;           //设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≤100000

输入样例：

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){do i++;while (p[i]<x);do j--;while (p[j]>x);if(i<j) swap(p[i],p[j]);}//分成前后两部分，然后不断递归，直至所有元素按顺序排列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]);}

下面这个案例通过不了

100000
15915 16204 16772 39929 49780 54646 77889 95421 99907 111172 121952 122706 124731 131398 139760 148589 155181 170780 175583 188205 212376 217320 221990 232051 239426 248803 254604 254673 264967 268169 269199 276115 300535 320678 326159 343556 360571 364829 371381 377226 382586 384554 392322 424697 431253 445607 458868 461257 462269 462718 471566 495039 500714 531706 535351 546189 598985 605570 608169 613225 620863 621772 621961 622137 627701 630193 640276 649408 681872 696496 699171 701757 720370 721454 734730 737943 763532 770863 777830 798750 807871 813234 815923 817637 818637 848772 854192 859020 863563 869743 891206 906042 911164 927131 934261 937119 942289 978503 998519 1012979 1097505 1098574 1100041 1108883 1120574 1122034 1127503 1135396 1154850 1168703 1180078 1201147 1220407 1220776 1225060 1226999 1234379 1245895 1250079 1265821 1267700 1273550 1273763 1273926 1283855 1307052 1341878 1347086 1359513 1394362 1408506 1414060 1420067 1427682 1440646 1442642 1451958 1453582 1471274 1494703 1502278 1516591 1529917 1540677 1569316 1592346 1606577 1608654 1624278 1627103 1630514 1630737 1636008 1640086 1646308 1649628 1666459 1667332 1667807 1685189 1699255 1706371 1707828 1709570 1742037 1747728 1752040 1759841 1760306 1760735 1767907 1776488 1791896 1800481 1807411 1810027 1814428 1815449 1822032 1823800 1846352 1854440 1861090 1870495 1882156 1886069 1892128 1901710 1908498 1917505 1926331 1944882 1947042 1956168 1958502 1998742 2020980 2025295 2048831 2055746 2056233 2057170 2059619 2066864 2067131 2080478 2082421 2091404 2100097 2121441 2145666 2171123 2195198 2198673 2201081 2203998 2221169 2225421 2234497 2245383 2250376 2255023 2256200 2262075 2278943 2280415 2303991 2307401 2308518 2322320 2324184 2329125 2333602 2343849 2349531 2353410 2380408 2383118 2385012 2395403 2408273 2425489 2430119 2432622 2437419 2444271 2458042 2469823 2471846 2475428 2481559 2482620 2498788 2503102 2512559 2513103 2519955 2521968 2536834 2548583 2550327 2553713 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≤100000

输入样例：

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≤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;//只要大于等于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>>1if(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

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