指针与算法：排序、查找与字符串匹配

指针和算法，这两个东西放在一起，很多人第一反应是「头大」。其实没那么复杂。我做了十几年嵌入式开发，指针用得最多的场景，恰恰就是算法实现。今天咱们就聊聊排序、查找、字符串匹配这些经典算法里，指针到底扮演了什么角色。

排序算法中的指针交换

先说说排序。你写冒泡排序、快速排序，核心操作是什么？交换元素。对吧？

交换两个整型变量，你可能会这么写：

int temp = a;
a = b;
b = temp;

但如果交换的是结构体呢？比如一个包含 1KB 数据的结构体：

struct big_data {
    char buffer[1024];
    int id;
    double value;
};

直接交换两个结构体变量，C 语言会做一次内存拷贝，1024 字节搬来搬去。效率？你自己想想看。

这时候指针就派上用场了。

我们不交换结构体本身，只交换指向它们的指针：

struct big_data *pa, *pb, *ptemp;
ptemp = pa;
pa = pb;
pb = ptemp;

一次指针赋值，4 个字节（32位系统）或 8 个字节（64位系统）搞定。比搬 1KB 数据快了两个数量级。

我在项目中遇到过一个问题：一个嵌入式设备上跑排序算法，数据量不大，但每个元素是一个 2KB 的日志结构体。一开始直接交换结构体，排序花了 3 秒多。改成指针交换后，降到 0.2 秒。嗯，差距就这么大。

查找算法中的指针优化

二分查找，大家都会写。但用指针实现，有个好处——避免数组越界。

看这段代码：

int* binary_search(int* arr, int size, int target) {
    int* left = arr;
    int* right = arr + size - 1;
    
    while (left <= right) {
        int* mid = left + (right - left) / 2;
        if (*mid == target) return mid;
        else if (*mid < target) left = mid + 1;
        else right = mid - 1;
    }
    return NULL;
}

注意看 mid = left + (right - left) / 2。为什么不用 (left + right) / 2？

因为指针相加是未定义行为。你想想看，两个指针相加，结果指向哪里？没人知道。但指针相减，得到的是两个地址之间的元素个数，这是合法的。

另外，用指针做查找还有一个好处：返回值天然就是地址。你找到元素了，直接返回指针，调用方拿到指针就能读写这个元素，不需要再通过下标去换算地址。

字符串匹配算法（KMP）的指针实现

KMP 算法，很多人觉得难。其实它的核心就一句话：匹配失败时，利用已匹配部分的信息，跳过不必要的比较。

用指针实现 KMP，比用下标更直观。因为字符串本身就是字符数组，指针操作天然适合。

先看 next 数组的指针实现：

void get_next(const char* pattern, int* next) {
    int i = 0;
    int j = -1;
    next[0] = -1;
    
    while (pattern[i] != '\0') {
        if (j == -1 || pattern[i] == pattern[j]) {
            i++;
            j++;
            next[i] = j;
        } else {
            j = next[j];
        }
    }
}

再看匹配过程：

const char* kmp_search(const char* text, const char* pattern) {
    int next[256];
    get_next(pattern, next);
    
    int i = 0, j = 0;
    while (text[i] != '\0' && pattern[j] != '\0') {
        if (j == -1 || text[i] == pattern[j]) {
            i++;
            j++;
        } else {
            j = next[j];
        }
    }
    
    if (pattern[j] == '\0') {
        return &text[i - j];  // 返回匹配位置的指针
    }
    return NULL;
}

你看，返回的是 &text[i - j]，一个指向匹配起始位置的指针。调用方拿到这个指针，可以直接从这个位置开始处理，不需要再算下标。

递归与指针

递归和指针结合，最常见的场景就是链表和树的操作。比如反转链表：

struct node* reverse(struct node* head) {
    if (head == NULL || head->next == NULL) {
        return head;
    }
    struct node* new_head = reverse(head->next);
    head->next->next = head;
    head->next = NULL;
    return new_head;
}

这段代码，说白了就是：先递归到链表末尾，然后从后往前，逐个反转指针方向。

递归的深度取决于链表长度。如果链表有 10000 个节点，递归深度就是 10000。栈空间够吗？

我建议你在嵌入式系统里慎用递归。因为嵌入式设备的栈通常很小，可能只有几 KB。递归深度稍微大一点，栈就溢出了。

递归和指针还有一个经典组合：函数指针实现回调。比如快速排序的 qsort()，它的比较函数就是通过函数指针传入的。这种设计模式在算法库中非常常见。

知识体系总览

下面这张图，把指针在算法中的几个核心应用场景串起来了：

这张图展示了指针在算法中的四个主要应用方向。每个方向都有它的独特价值，但核心思想是一致的：指针操作的是地址，地址操作比数据操作更轻量、更灵活。

小结

指针和算法结合，说白了就是两件事：

• 用指针代替数据——排序时交换指针，查找时返回指针，减少数据搬运
• 用指针控制流程——递归遍历链表树，函数指针实现回调，让代码更灵活

我在实际项目中，80% 的算法优化都跟指针有关。不是算法本身有多复杂，而是数据怎么搬、地址怎么算，这些细节决定了最终性能。

嗯，这一章就到这里。记住一句话：指针不是洪水猛兽，它是 C 语言给你的一把手术刀——用好了，精准高效；用不好，割到自己。

---