查找
1.1 二分查找法（ ** 前提：有序序列+顺序存储结构！** ）--时间复杂度位O(logn)
定义：对于一个给定序列中，每一趟都选取中间位置的元素值与给定关键词做比较，从而确定下一次查阅的范围，不断缩小范围查找，直到找到/确定找不到为止
以下代码没有考虑有重复元素的情况
bool mid_search(int *a,int n_a,int val)
{
if(n_a==0)
return false;
int low=0;
int high=n_a-1;
while(low<=high)
{
int mid=low+(high-low)/2;
if(val==a[mid])
return true;
else if(val>a[mid])
low=mid+1;
else if(val<a[mid])
high=mid-1;
}
return false;
}1.2 哈希查找
哈希查找分两部分：插入+查找
原理是利用哈希函数找到哈希表中的哈希地址，然后再哈希表中存放元素信息，便于之后的查找，然后再次利用哈希函数得到哈希地址，在哈希表中找到元素信息，从而快速找到关键词！
一般我们都是使用给定的hash函数，然后去实现哈希表的构建，元素信息的存放以及查找！！！
这里需要注意的是，一定要知道哈希函数的构建方法以及哈希冲突的定义及减少冲突的方法有哪些！！！
1.3 顺序查找
- 八大排序
1、插入排序 1.1直接插入排序 1.2shell排序
2、选择排序 2.1 直接选择 2.2堆排序
3、交换排序 3.1冒泡排序 3.2 快速排序！！！！！考察的相对较多
4、归并排序
5、基数排序 ？？？？
几个概念：
内部排序：排序期间元素全部存放在内存中的排序；
外部排序：排序期间元素无法全部存放在内存中，必须在排序过程中根据要求不断地进行内外存之间移动地排序；
(这八种排序算法中除了多路归并排序是外部排序，其他都是内部排序)
稳定性：指的是经过排序后，值相同的元素保持原来顺序中的相对位置不变.
各算法时间复杂度、空间复杂度、所需辅助空间与稳定性如下：
对于这些排序，要做到
1、知道思想
2、代码很熟练的写出来
3、每一种排序常见的几种方法/可以优化的地方要熟练掌握，各种表示方法之间的优缺点对比（除了快排，其他排序方法是代码上的不同及对应代码上的优化）
4、运用场合及时间、空间复杂度
判断排序方法是否稳定，即稳定排序算***依照相等的关键（换言之就是值）维持纪录的相对次序。注意是相对次序，即在前的还是在前，在后的还是在后，具体方向是这样的
一个排序算法是稳定的，就是当有两个有相等关键的纪录R和S，且在原本的串列中R出现在S之前，在排序过的串列中R也将会是在S之前。
1.1 直接插入排序
思想：在一个有序序列中插入待排关键词，即在这个有序序列中找到自己的位置，
加入以后仍然组成一个有序序列，这就以为着一旦要移动，待排关键词所要在的位置之后所有元素都要往后移动
平均时间复杂度O（n2） 最好情况O（n） 最坏情况O（n2）空间O（1） 稳定
优点：稳定
缺点：每次比较的次数不一定，比较次数越多，插入位置之后数据量庞大的时候，效率很低
代码如下：
void intersort(vector<int> wait)//假设待排的都是整数，放在容器/数组中
{
if(wait.size() ==0||wait.size() ==1)
return ;
int n = wait.size();
for(auto i =1;i<n;++i) //遍历存放待排序关键词的容器，将他们正确的放入有序序列中
{
int tmp =wait[i];
auto j = i-1; //每次只需和前一个元素先比较即可，因为之前的都是有序序列
while(wait[j] >wait[i] &&j>=0)
{
wait[j+1]=wait[j];
--j;
}
wait[j+1]=tmp; //跳出循环的j的位置是比待排的元素小的，说明其下一个位置是我们要放入的位置
}
return ;
}
1.2希尔排序===》直接插入排序（n小+序列基本有序 ==效率高）==》最后的gap一定是1！！！
思想:将待排的关键词序列以相邻某个间隔gap为相邻关键词组成若干个子序列，并分别进行直接插入排序，然后不断缩减间隔gap,不断的实现序列基本有序，（刚开始的时候分组多，数据少，后面是分组少，数据多。）直至最后间隔一定为1，即对整个序列进行直接插入排序，从而实现希尔排序
时间复杂度使O（n 1.3）最好情况O（n） 最坏情况O（n2） 空间复杂度O（1） 不稳定
希尔一开始取间隔是取n/2向下取整，缺点是但由于直到最后一步，在奇数位置的元素才会与偶数位置的元素进行比较，这样使用这个序列的效率会很低。
适合运用在已知长度序列，小数组的情况下，数据量较大的情况并不如快排
相应代码为：
void shell_sort(vector<int> vec)
{
if(vec.empty() ||vec.size() ==1)等情况
for(int gap =n/2;gap>0;gap/=2) //不断缩减间隔，最后一定为1
{
int n =vec.size();
for(auto i =gap;i<n；++i) //在待插入序列中，选取关键词插入
{
for(auto j =i;j>=gap&&vec[j] <vec[j-gap];j-=gap) //在序列中找到自己得位置
{
swap(vec[j],vec[j-gap]);
}
}
}
return ;
}也有间隔取n/3向下取整+1 ,对于gap的划分，没有说谁对谁错，看应用的场合
很明显，gap变成1得速度变快了，可以说变成有序得速度变快了，
相应代码如下：
void shell_sort(vector<int> vec)
{
。。。。。。。。。(空/仅有一个元素等的情况)
int n = vec.size();
int gap =1; //最后间距一定是1
while(gap<n/3)
gap=gap*3+1; //选取不大于数组长度得第一个间隔
while(gap>=1)
{
for(auto i =gap;i<n;++i) //选取待排关键词
{
for(auto j =i;j>=gap && vec[j] <vec[j-gap];j-=gap) //在对应得序列中找到自己得位置
{
swap(vec[j],vec[j-gap]);
}
}
gap/=3; //不断缩小间隔，直至最后gap=1;
}
}
2.1 选择排序（两个属于选择排序的时间复杂度，各自最好情况最坏情况平均情况都是一样好的）
思想：重在选择二字，即在待排关键词序列中选出最小/最大的，放置序列的第一位，同时不断缩小序列范围，从而实现将序列变成有序。
时间复杂度：O（n2）最好情况O（n2） 最坏情况O（n2） 空间复杂度O（1） 不稳定
相应代码：
void select_sort(vector<int> vec)
{
。。。。。。。。。(空/仅有一个元素的情况)
int n=vec.size();
for(auto i =0;i<n-1;++i) //选择要放置的位置，即序列的这个位置放置相对于之后的所有元素来说最小的元素
{
for(auto j =i+1;j<n;++j)//要放置的位置与之后的元素相比较得到最小的元素，并放置在对应位置
{
if(vec[i]>vec[j])
swap(vec[i],vec[j]); //交换的是内容！！！
}
}
return ;
}
这里可以优化的地方是对于放置元素那一块，可以先找到序列中最小的元素下标，然后最后再与要放置的位置交换，减少了交换次数，提高效率
void select_sort(vector<int> vec)
{
。。。。。。。。。(空/仅有一个元素的情况)
int n =vec.size();
int min =0;
for(auto i =0;i<n-1;++i) 相应序列要存放其最小元素的位置
{
min=i;
for(auto j =i+1;j<n;++j) //找到最小元素的下标
{
if(vec[j] <vec[min])
{
min=j;
}
}
swap(vec[i],vec[min]); //放于相应序列的第一个位置
}
return;
}2.2堆排序（将根节点编号为1，即完全二叉树是以1开始计数的！）
思想：堆排序的含义是：以堆的特性对待排序列进行排序，堆的特性有两个1、结构性（完全二叉树的结构）2、堆序性（每个结点不小于/不大于子节点）
所以换句话说，假设我们采用数据结构来记录无序、有序的待排关键词的话，就是将这个数组里面的无序序列经以完全二叉树的逻辑思想及堆序性
变成有序序列！！！---实质是对数组进行操作，但是思想逻辑用的是完全二叉树的
需要解决两个问题
1、将无序序列变成具有堆特性的序列
2、输出堆顶以后，重新排序，排成具有堆特性的序列
堆排序在最坏情况下的时间复杂度是O(nlogn) ; 空间复杂度是O(1)，在所有的事件复杂度为 O(nlogn)的排序算法中，是最小的。
堆排序适合关键字很多的情况，典型的例子是从10 000个关键字中选择出前10个最小的。如果关键字比较少，不建议使用堆排序。
void heap_sort(vector<int> vec)
{
vec为空等情况....
int n =vec.size();
/*****************将无序序列编程具有堆特性的序列********************/
for(auto i =n/2;i>=1;--i)//为了将整个序列都变成具有堆序性的序列
{
sift(vec,i,n);//这里我们将其定义为至上而下的保证堆序性（每个结点不小于/不大于子节点）！！
}
//接下来就是提取出我们要的最大/最小元素以后，再次排序，排成具有堆序性的序列
for(auto i =n;i>=2;--i) //将所有的待排的关键词都遍历以堆排序的方式进行数组的排序
{
int tmp =vec[1];
vec[1] =vec[i]; //单独拿掉最后一个元素是不会影响原有的堆序性
vec[i] =tmp;
sift(vec,1,i-1); //不需要加循环，因为已经基本有堆序性了，//将无序序列变成具有堆特性的序列
}
}
以大顶堆为例对无序序列的筛选：
void sift(vector<int> vec,int low ,int high)
{
vec为空等情况....
int i =low;
int j =2i; //左结点
int tmp = vec[i];
while(j<=high) //保障堆序性换句话说就是找到各个树中各自结点的位置
{
if(j<high&&vec[j] <vec[j+1]) //小顶堆的话该这个地方
{
++j; //j指向大的结点
}
if(tmp <vec[j]) //保证堆序性 // 小顶堆的话该这个地方
{
vec[i] =vec[j];
i=j; //保障至上而下的堆序性
j=2i;
}
else
{
break;
}
}
vec[i] =tmp; //将根结点放入符合堆排序的位置
return;
}
3.1 冒泡排序
思想：从第一个元素与相邻元素相比较，大的在后，小的在前，不断比较，将最大的放置序列的最后，然后不断从后往前缩小序列大小，最后
实现排序
平均时间复杂度是O（n2） 最好时间复杂度是O（n） 最坏时间复杂度是O（n2）空间复杂度O（1）
优点：稳定
缺点：每次是两个元素的比较/移动，一趟下来较慢
相关代码：
void Bubble(vector<int> vec)
{
vec为空等情况。。。。
int n =vec.size();
int flag=0; 这个是可以优化的地方！！！ //如果一趟冒泡排序下来，没有变动，可以直接结束，不需要等全部遍历完再结束
for(auto i =n-1;i>=1;--i) //控制序列的范围，不断的实现序列从后往前递减
{
flag=0;
for(auto j =0;j<n-1;++j) //一次比较相邻元素，使大的在后小的在前，不断的比较交换，相当于不断在序列中取出最大值依次放于序列的最后端
{
if(vec[j]>vec[j+1])
{
swap(vec[j],vec[j+1]);//也可以用tmp当临时值来取代swap算法
flag =1;
}
}
if(flag ==0)
return ;
}
return ;
}3.2快速排序 ！！！！！考察的相对较多--最坏情况是O(n2)，发生在待排序列是正序/逆序的情况下！（感觉每一趟都在做无用功），最优的情况是每一次选取的枢轴都是所在子序列的中间位置，
思想：由于冒泡排序每从而往前缩小一次序列范围，全部的元素都要重新进行比较，这样效率太低======》首先选定枢轴（通常是序列的首个元素），
将序列分成以枢轴为中心的两部分，枢轴左边小于其，枢轴右边大于其，然后不断的对左边右边进行相同的操作，直到实现整个序列有序
代码上主要优化（变化）的地方是pivot的值与交换。
优点：相对于冒泡排序来说，一趟排序速度较快-----因为双指针
缺点：不稳定
平均时间复杂度是O（nlogn）,最好时间复杂度是O（nlogn）,最坏时间复杂度是O（n2）,空间复杂度O（logn） 不稳定 快速排序是内部排序中，算法的平均性能最优的排序算法。
适合运用于序列无序程度较高即比较乱的情况下，效率高，若局部有序程度较高的情况下步入插入排序
还有类似于求数组中第k的元素的场景，运用快排比较好
还可以再优化的地方：（思想逻辑上加入别的）
1、当序列被分割成一定大小的若干子序列的时候，可以使用插入排序
原因：对于很小和部分有序的数组，快排不如插排好，插入排序稳定。
当待排序序列的长度分割到一定大小后，继续分割的效率比插入排序要差，此时可以使用插排而不是快排。
2、在一趟快排结束后，可以出去不必要的调换，即将==pivot的值放在中间一起，下次再分割的时候从!=的元素开始
3、pivot的选取，可以尽量选择能够平均分割序列的枢轴！
相应代码：
void Quick_sort(vector<int> vec,int low,int high)
{
vec为空等情况。。。。
if(low<high)
{
int i =low; //为了最后递归的时候，写起始位置、终止位置
int j=high;
int pivot=vec[low];
while(i <j)
{
while(j>i &&vec[j] >=pivot) //==的意思是表示最后求出的位置出去比他小的出去比他大的元素之外的一定范围之内都是他的！！！
--j;
if(j>i) //排除掉是因为i==j的情况
{
vec[i] =vec[j];
++i;
}
while(j>i &&vec[i] <=pivot)
++i;
if(j>i) //排除掉是因为i==j的情况
{
vec[j] =vec[i];
--j;
}
} //i==j的时候退出循环，表示第一趟快速排序结束,不要忘记一个不完美之处，就是i处要赋值pivot才对
vec[i] =pivot;
Qucik_sort(vec,low,i-1);
Quick_sort(vec,i+1,high); //通过递归多趟快速排序
}
return ;
}
4、归并排序
思想：分而治之的思想，通俗一点讲就是首先将一个无序序列不断的划分，直到分成若干的有序序列（只有一种情况），就是分成一个元素表示一个序列的情况
即实现若干有序序列，然后合并，不断的两两有序合并，最终实现整个序列的排序，大致步骤是：分===》若干有序的序列=====》有序合并
平均时间复杂度是O（nlogn）,最好时间复杂度是O（nlogn）,最坏时间复杂度是O（nlogn）,空间复杂度O（n） 稳定
适合运用于数据量较大并且要求排序稳定的情况下
相应代码：
void Merge_sort( vector<int> vec,int low,int high)
{
vec为空等情况。。。。
if(low<high)
{
/*********************首先进行划分===》若干有序序列*****************/
int mid =(high-low)/2;
Merge_sort(vec,low,mid);
Merge_sort(vec,mid+1,high);
//然后有序合并
merge(vec,low,mid,high);
}
}
void merge (vector<int> vec,int low,int mid ,int high) //实现有序合并，有序的放入vec中
{
vec为空等情况。。。。
if(low<high)
{
/************************开始进行有序合并*******************************/
int n1= mid-low+1; //要合并的左半部分
int n2 =high-mid; //要合并的右半部分
/*****************合并的是元素，所以需要创建两个数组分别存放要合并部分的元素！！！*****************/
int L1[n1],L2[n2] ;
int i =0;
int j =0;
for(i =0;i<n1;++i)
L1[i] =vec[low+i];
for(j =0;i<n2;++j)
L2[j] =vec[mid+1+j];
/********************进行有序的合并放入vec中*************************/
i=0;//对于L1数组的下标
j=0;//对于L2数组的下标
k=0;//对于vec数组的下标
while(i<n1 &&j<n2)
{
if(L1[i]<L2[j])
vec[k++]=L1[i++]; //k++一定是这样的！！！
else
vec[k++]=L2[j++];
}
while(i<n1)
vec[k++]=L1[i++];
while(j<n2)
vec[k++]=L1[j++];
}
}
京公网安备 11010502036488号