三种基础算法学习

发表于2023-01-16更新于2023-07-12字数统计1.9k阅读时长11分阅读次数阅读次数

一、归并排序

1、算法思想

其实这些排序算法都是很基础的东西，要是有考试的话直接sort就够用，但是目的还是学习思想，有些题用这些算法里面的思想可能会有奇效。

（一）归并排序思想：

  1. 先确定分界点，就是区间中点mid = (l+r) / 2

  2. 先两侧递归，即先递归左面排序，后递归右面排序

  3. 将上面两个排好序的序列合二为一，用到的是双指针算法

（二）双指针算法

简单来说就是两个指针分别指向两个有序数列（默认从小到大）的开头，比较两个指针指向的数字，这两个数中较小的数一定是两个序列的最小的数，填入新数组的开头，然后较小的数的指针加一，以此类推

（三）稳定性

归并排序是稳定的。稳定的含义简单来说就是在未排序之前两个数的相对位置和排序之后两个数的相对位置一致。就比如排序前a在b左边但是a=b，排序后a仍在b左边，不会在b右边，这就是稳定性。

一般用于对某个对象的属性进行排序的时候，这个对象有多个属性时，比如价格，性价比两项，先对价格进行排序，排好之后再对性价比进行排序，但是要求对相同性价比的商品价格低的优先级仍高于价格高的优先级（即已有a=b，此时ab指代性价比，需要仍保持ab之前的排序不变，即价格的高低顺序一致），而不会反过来，这时候的排序算法就需要有稳定性的排序算法。而不稳定的排序算法（如快排）就会有可能使当a=b的时候ab的相对顺序和之前不一致。

2、代码示例（模板来咯）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int tmp[N];
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];
}

其实这种基础算法归根结底学的是思想，思想应该更加重要。

二、快速排序

1、基本思想

快速排序的基本思想十分简单，如下图，其中调整位置并且递归是主体部分，下面我将放出朴素快速排序和最近学到的一种很新的快速排序代码方式，正所谓背模板嘛。仅供参考。

（字丑请见谅）

注意 ：x位置也可以是随机的，不一定在中点或者左右端点。

2、代码如下：

（一）朴素快速排序算法：

本来想敲一遍的，但是发现朴素算法不够优雅肯定用不到，所以就讲一下基本思路就好了

  1. 建立两个数组a[N]与b[N]；

  2. 对q[x]进行扫描，大于等于x的放到a里面，小于x的放到b里面

  3. 最后把a里面的数放到q前面，然后紧接着把b里面的数放到q里面完成。

  4. 然后分别对左右两边递归。结束

这种算法的时间复杂度不大，仍是O(n)（指一次递归过程中，不是总的时间复杂度），但是用到了额外的空间，空间复杂度较高。下面这种“优雅”的方法可以有效避免这一点。

（二）优雅的快排算法

基本思路，用到两个指针i，j；

  1. i 指针负责判断指向的数是否小于x，如果符合条件，则自增，如果指向的数 \leq x，停止移动

  2. j 指针负责判断指向的数是否小于x，如果符合条件，则自增，如果指向的数 \geq x，停止移动

  3. 如果i指针和j指针同时停止移动，则交换两指针指向的内容，保证了i指针所指向的数之前全部小于x，j指针指向的数之后均大于x；

  4. 当i指针\geq j指针后，停止循环

  5. 然后以l到j，j+1到r为分界分别递归

代码如下

1
2
3
4
5
6
7
8
9
10
11
12
void quick_sort(int q[],int l,int r){
    if(l >= r) return;
    int i = l-1, j = r+1;
    int x = q[(l+r)/2];
    while(i < j){
       do i++; while(q[i] < x);
       do j--; while(q[j] > x);
       if(i < j) swap(q[i],q[j]);
    }
    quick_sort(q,l,j);
    quick_sort(q,j+1,r);
}

这种方法就有效避免了额外再开辟空间的情况，空间复杂度较好。

三、二分法

1、算法思路

二分查找主要分为两类，一类是整数二分查找，一类是实数二分查找。整数二分查找比较困难，因为边界问题很多，需要考虑的事情很多，下面说一下二分查找的基本思路。

注：有单调性的一定可以用二分，没有单调性的不一定不能用二分，二分的本质并不是单调性，关系并不是很大

如上图，整数二分的本质并不在单调性，只不过大部分例子都是单调性有关而已。而实际的本质是把一个区间按某个性质分为两段，（由于是整数二分则上面两段的箭头指向的端点并不重合），通过二分就可以分别找出两个箭头所指向的位置。而正由于有两个区间的端点，因此有两个模板分别求这两个箭头指向的位置。简单来说：

  • 左侧箭头指向的是符合红色条件的最右侧的位置

  • 右侧箭头指向的是符合绿色条件的最左侧的位置

为方便理解，可以以一道经典例题为例：

给定一个按照升序排列的长度为 n的整数数组，返回一个元素 k的起始位置和终止位置（位置从 0开始计数）如果数组中不存在该元素，则返回 -1 -1。

即如果序列为1,2,3,3,3,4,5,5，需要返回3的起始位置和终止位置，则用二分较快。其中起始位置的3就代表上图右侧箭头，指向的是符合绿色条件的最左侧的位置，即此处的3把整个区间按性质：是否大于等于3分成两半。左侧均小于三，右侧均大于等于3；终止位置3就代表上图左侧箭头，指向的是符合红色条件的最右侧位置，即此处的3把整个区间按性质：是否小于等于3分成两半。左侧均小于等于三，右侧均大于3

因此，像这种找区间左右端点的题就需要分别使用两种模板，如下：

2、代码模板

(一)、整数模板
1
2
3
4
5
6
7
8
9
10
11
12
// 模板一
while(l < r){
    int mid = l + r >> 1;
    if(check(mid)) r = mid;
    else l = mid + 1;
}
//模板二 if后面跟l就加一
while(l < r){
    int mid = l+ r + 1 >> 1;   // +1是为了防止死循环
    if(check(mid)) l = mid;
    else r = mid - 1;
}

注意：L = mid 时，初始化mid的时候需要+1，是为了防止死循环