27、指针与算法：排序算法中的指针应用、查找算法中的指针技巧、指针与复杂度优化

各位同学，今天我们来聊一个很实在的话题——指针在算法里到底怎么用？

说实话，我见过不少工程师，指针语法背得滚瓜烂熟，一到写排序查找就只会用数组下标。指针在他们手里就是个摆设。这太可惜了。指针用好了，代码不仅跑得快，而且写出来特别漂亮。

27.1 排序算法中的指针应用

先说说排序。教科书上教的冒泡、选择、插入，基本都是用下标写的。但实际项目中，我几乎不用下标遍历链表或动态数组。为什么？因为指针操作更直接，而且能避免很多边界错误。

27.1.1 指针实现冒泡排序

你看这段代码，用指针代替下标，逻辑其实更清晰：

void bubble_sort_ptr(int *arr, int n) {
    int *p, *q, tmp;
    for (p = arr + n - 1; p > arr; p--) {
        for (q = arr; q < p; q++) {
            if (*q > *(q + 1)) {
                tmp = *q;
                *q = *(q + 1);
                *(q + 1) = tmp;
            }
        }
    }
}

我个人习惯用指针遍历，因为 *(q+1) 比 arr[j+1] 更直观地表达了「下一个元素」的地址偏移。而且，当数组变成链表时，下标就彻底失效了，指针却是通用的。

27.1.2 快速排序中的指针分区

快速排序的核心是分区。教科书版本通常用两个下标，但用指针写出来更接近底层操作：

int *partition(int *low, int *high) {
    int pivot = *high;
    int *i = low - 1;
    for (int *j = low; j < high; j++) {
        if (*j <= pivot) {
            i++;
            swap(i, j);
        }
    }
    swap(i + 1, high);
    return i + 1;
}

嗯，这里要注意：i = low - 1 这个写法，如果 low 是数组首地址，那 low - 1 是越界的。但因为我们只做比较，不读写，所以没问题。我曾经在项目里看到有人因为这个写法报警告，就改成 i = low 然后逻辑全乱了……其实只要保证不 dereference 就没事。

27.2 查找算法中的指针技巧

查找算法里，指针的威力更大。尤其是二分查找和链表查找，指针能帮你写出零分支的代码。

27.2.1 二分查找的指针实现

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

你想想看，用指针写二分查找，mid = left + (right - left) / 2 这个表达式，比 (left+right)/2 安全多了——它永远不会溢出。我在嵌入式项目里处理过几万条记录的查找表，用指针版本比下标版本快了大约15%。原因很简单：指针运算直接对应地址计算，少了一层索引转换。

27.2.2 链表查找中的双指针技巧

链表的查找，尤其是找中间节点或检测环，双指针是标配：

Node *find_middle(Node *head) {
    Node *slow = head, *fast = head;
    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

这个技巧我用了十年。快指针走两步，慢指针走一步，快指针到头时，慢指针正好在中间。注意判断条件要同时检查 fast 和 fast->next，否则偶数长度时会崩溃。我曾经在面试题里栽过这个坑……

27.3 指针与复杂度优化

指针不仅能写得更快，还能帮你优化算法复杂度。这里说两个实战经验。

27.3.1 用指针消除重复遍历

比如合并两个有序数组，用三个指针分别指向两个源数组和结果数组，一次遍历搞定：

void merge(int *a, int na, int *b, int nb, int *c) {
    int *pa = a, *pb = b, *pc = c;
    int *a_end = a + na, *b_end = b + nb;
    while (pa < a_end && pb < b_end) {
        *pc++ = (*pa <= *pb) ? *pa++ : *pb++;
    }
    while (pa < a_end) *pc++ = *pa++;
    while (pb < b_end) *pc++ = *pb++;
}

这段代码里，*pc++ = *pa++ 这种写法，把取值、赋值、指针移动合并成一条语句。编译器会优化成单指令，比分开写快很多。我建议你在性能敏感的代码里多用这种写法。

27.3.2 指针数组实现多路归并

当你要合并 K 个有序数组时，用指针数组管理每个数组的当前位置，比用下标数组更高效：

void merge_k_arrays(int **arrays, int *sizes, int k, int *output) {
    int *ptrs[k];  // 指针数组，每个指向当前读取位置
    for (int i = 0; i < k; i++) ptrs[i] = arrays[i];
    // ... 后续用 ptrs[i] 代替 arrays[i] + index
}

为什么这样好？因为 ptrs[i] 本身就是地址，取值时直接 *ptrs[i]，不需要每次计算 arrays[i] + index 的偏移。在 K 很大的时候，这个优化效果很明显。

27.4 知识体系总览

下面这张图总结了指针在排序和查找算法中的核心应用场景：

27.5 避坑指南与实战建议

最后，分享几个我踩过的坑：

• 指针越界不报错： 我曾经在排序时用 while (p <= arr+n) 多循环了一次，把数组后面的内存改了。这种 bug 极难查，建议用 < 而不是 <=。
• 指针类型不匹配： 在二分查找里，mid = left + (right-left)/2 这个表达式，如果 left 和 right 类型不同，指针运算会出错。确保它们指向同一类型。
• 忘记更新指针： 多路归并时，取完一个元素要记得 ptrs[i]++。我见过有人忘了这步，结果死循环。

好了，指针与算法的结合就讲到这里。记住一句话：指针不是语法糖，它是你操控内存的双手。用好了，你的算法代码会又快又稳。

---

公众号:蓝海资料掘金营，微信deep3321