本节内容为部分排序和查找算法，数据结构课讲过，不过当时期末时间紧，没去听课，虽然PPT看懂了，但是从没有自己完整敲过，现在原理也都忘了，学一遍发现确实有些地方容易写错。

快速排序

核心思路

主要思想：分治

1. 确定分界点：q[l]或者q[(l+r)/2]或者q[r]；
2. 调整范围：目标是左边的数都小于等于x，右边的数都大于等于x（分界点不一定是x）；
3. 递归处理左右两端

第2步实现

暴力算法

1. 开两个数组a[ ]和b[ ]；

2. 把q[ ]中从l到r遍历：

   • q[i]<=x 放入a;
   • q[i]>x 放入b;
3. 把a[ ]和b[ ]放入q[ ]中

常用思路

1. 设定两个指针，从左右两端开始：

   • 左指针从左向右寻找第一个大于等于基准的元素
   • 右指针从右向左寻找第一个小于等于基准的元素
2. 找到之后交换两个元素

3. 持续移动左右指针并交换元素，直到两个指针相遇，此时结束

   代码

自己手写了一遍：

void quicksort(int a[], int l, int r){
    if(l>=r) return;
    int cha = a[l];
    int x = l+1, y = r;
    while(x<=y){
        while(x<=y){
            if(a[x]>cha) break;
            x++;
        }
        while(x<=y){
            if(a[y]<cha) break;
            y--;
        }
        if(x<y){
            swap(a[x],a[y]);
        }
    }
    swap(a[l],a[y]);
    if(l<y)quicksort(a,l,y-1);
    if(y+1<r)quicksort(a,y+1,r);
}

老师给的代码：

void quicksort(int q[], int l, int r){
    if(l>=r) return;
    int x = q[l], i = l - 1, j = r + 1; //此处-1和+1都是为了后面do while简洁
    while(i < j){
        do i++; while (q[i] < x);
        do j--; while (q[j] > x);
        if(i<j) swap(q[i],q[j]);
    }
    quicksort(q,l,j);//取j时前面不能是x = q[r]
    quicksort(q,j+1,r);
    //quicksort(q,l,i-1); 取i时前面不能是x = q[l]
    //quicksort(q,i,r);
}

STL的快速排序函数

#include <algorithm>
std::sort(arr, arr + n);

默认从小到大，范围为数组arr到arr+n-1

重构：指定cmp排序函数（以结构体为例）：

#include <iostream>
#include <algorithm>
using namespace std;

struct Person {
    string name;
    int age;
};

bool cmp(const Person& a, const Person& b) {
    return a.age < b.age; // 按年龄升序
}
//这里使用(const Person& a, const Person& b)是因为节省空间，使 用引用类型，避免再复制一份变量，使用const是防止函数修改原来的值，const是保护措施。

int main() {
    Person arr[] = { {"Alice", 30}, {"Bob", 25}, {"Charlie", 35} };
    int n = sizeof(arr) / sizeof(arr[0]);

    sort(arr, arr + n, cmp);

    for (int i = 0; i < n; i++) 
        cout << arr[i].name << " " << arr[i].age << endl;
    // 输出：
    // Bob 25
    // Alice 30
    // Charlie 35

    return 0;
}

归并排序

主要思路

主要思想：分治

1. 确定分界点: $mid = \frac{l + r}{2}$
2. 递归排序左边和右边
3. 合并两个数组为一个数组（归并）

代码

int linshi[100000];
void binggui(int a[], int l, int r){
    if(l>=r) return;
    int mid = (l+r)/2;
    binggui(a,l,mid);
    binggui(a,mid+1,r);
    int i = l, j = mid + 1;
    int now = l;
    while(i<=mid&&j<=r){
        if(a[i]>a[j]) linshi[now++] = a[j++];
        else linshi[now++] = a[i++];
    }
    while(i<=mid) linshi[now++] = a[i++];
    while(j<=r) linshi[now++] = a[j++];
    for(int t = l; t <= r; t++) a[t] = linshi[t];
}

整数二分

有单调性一定可以二分，没有单调性也有可能二分。

步骤

1. 选取一个点 $mid = \frac{l + r + 1}{2}$ （$+1$ 是为了上取整，为了下面 $True$ 时不会出现区间变成 $[mid,r] = [l,r]$ 而产生循环）

2. $if(check(mid))$ （检查是否属于左半边，比如检查 $mid \le cha$ ）

   • $Ture$ -> 改变 $l=mid$
   • $False$ -> 改变 $r = mid - 1$

此时取得的是等值的最后一个

或者

1. 选取 $mid = \frac{l+r}{2}$ （此处同理，默认下取整，为了不会产生 $[l,r]$）

2. $if(check(mid))$ （检查是否属于右半边，比如检查 $mid \ge cha$ ）

   • $True$ -> 改变 $r = mid$
   • $False$ -> 改变 $l = mid + 1$

此时取得的是等值的第一个

代码

int bsearch(int a[], int l, int r){
    while(l < r){
        int mid = l + r >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    return l;
}

int bsearch(int a[], int l, int r){
    while(l < r){
        int mid = l + r + 1 >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    return l;
}

自带bsearch函数

必须要先引入cstdlib库。

定义

void* bsearch(
    const void* key,     // 你要找的东西的地址
    const void* base,    // 排好序的数组的首地址
    size_t nmemb,        // 数组里有几个元素
    size_t size,         // 每个元素多大（以字节为单位）
    int (*compar)(const void*, const void*)  // 比较函数的地址
);

举例

#include <iostream>
#include <cstdlib>  // bsearch在这里面

// 比较函数
int compare(const void* a, const void* b) {
    int va = *(const int*)a;
    int vb = *(const int*)b;
    if (va < vb) return -1;
    else if (va > vb) return 1;
    else return 0;
}

int main() {
    int arr[] = {1, 3, 5, 7, 9};  // 有序数组
    int n = sizeof(arr) / sizeof(arr[0]);
    int key = 5;

    // 用 bsearch 查找 key
    int* found = (int*) bsearch(&key, arr, n, sizeof(int), compare);

    if (found != nullptr) {
        std::cout << "找到了，值是: " << *found << std::endl;
    } else {
        std::cout << "没找到" << std::endl;
    }

    return 0;
}

浮点数二分

没有整除的考虑，所以简便一些。

举例：查找某个数的开根值。

#include <iostream>

using namespace std;

int main(){
    double x;
    cin >> x;

    double l = 0, r = x;
    while(r- l> 1e-8){
        double mid = (l + r)/2;
        if(mid*mid>=x) r = mid;
        else l = mid;
    }
    printf("%lf\n",l);
    return 0;
}