指针与排序算法：冒泡排序的指针实现、快速排序的指针实现、回调函数实现通用排序

排序算法，是每个嵌入式工程师都绕不开的基本功。我记得刚入行那会儿，面试官让我手写一个冒泡排序，我刷刷刷写完了，他看了一眼说：“能不能用指针改一下？”我当时一愣——用数组下标不是好好的吗？后来我才明白，指针操作在底层数据交换、内存受限的场景下，优势非常明显。

今天这一章，我们就来聊聊怎么用指针实现两种经典排序：冒泡和快速。最后再上一个“大招”——用回调函数把排序算法做成通用的，想排什么类型就排什么类型。

一、冒泡排序的指针实现

冒泡排序的原理很简单：相邻元素两两比较，大的往后“冒”。用数组下标写，大家都会。但用指针写，能让你更深刻地理解内存操作。

我个人习惯在嵌入式项目里用指针操作数组，因为很多底层寄存器、缓冲区都是地址连续的。你想想看，用指针自增去遍历，比用下标索引更贴近硬件思维。

#include <stdio.h>

void bubble_sort_ptr(int *arr, int n) {
    int *p, *q, tmp;
    for (int i = 0; i < n - 1; i++) {
        // p 指向数组起始，q 指向下一个元素
        p = arr;
        q = arr + 1;
        for (int j = 0; j < n - 1 - i; j++) {
            if (*p > *q) {
                tmp = *p;
                *p = *q;
                *q = tmp;
            }
            p++;
            q++;
        }
    }
}

int main() {
    int a[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(a) / sizeof(a[0]);
    bubble_sort_ptr(a, n);
    for (int i = 0; i < n; i++) {
        printf("%d ", a[i]);
    }
    return 0;
}

你看，这里 p 和 q 就是两个“游标指针”，每次比较完就一起后移。我在项目中调试过一段类似的代码，当时有个坑：内层循环的边界条件写错了，导致指针越界。嗯，这里要注意——指针移动一定要保证不超出数组范围。

二、快速排序的指针实现

快速排序是“分治思想”的典型代表。用指针实现时，核心是分区函数——它需要两个指针从两端向中间扫描。

我曾经在做一个数据采集系统时，需要对传感器数据实时排序。冒泡太慢，就换成了快排。当时用指针写分区函数，调试了一下午才跑通。说白了，指针的移动逻辑一旦理清楚，代码会非常简洁高效。

#include <stdio.h>

void swap(int *a, int *b) {
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

int *partition(int *low, int *high) {
    int pivot = *high;   // 选最后一个元素作为基准
    int *i = low - 1;    // i 指向小于基准的区域的最后一个位置

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

void quick_sort_ptr(int *low, int *high) {
    if (low < high) {
        int *pi = partition(low, high);
        quick_sort_ptr(low, pi - 1);
        quick_sort_ptr(pi + 1, high);
    }
}

int main() {
    int a[] = {10, 7, 8, 9, 1, 5};
    int n = sizeof(a) / sizeof(a[0]);
    quick_sort_ptr(a, a + n - 1);
    for (int i = 0; i < n; i++) {
        printf("%d ", a[i]);
    }
    return 0;
}

这里 partition 返回的是基准元素的指针。你注意看，i 初始化为 low - 1，这是为了在第一次比较时能正确工作。我刚开始写的时候，把 i 初始化为 low，结果分区逻辑全乱了。

三、回调函数实现通用排序

上面两个排序都只能排 int 类型。如果我想排 float、double，甚至结构体呢？难道每种类型都写一遍？

当然不用。C 标准库里的 qsort 就是最好的例子——它通过回调函数来比较任意类型的数据。我们完全可以模仿它，写出自己的通用排序函数。

说白了，就是把“比较”这个动作抽象出来，交给调用者决定。你想想看，这样代码的复用性一下子就上来了。

#include <stdio.h>
#include <string.h>

// 通用交换函数：按字节交换
void swap_bytes(void *a, void *b, size_t size) {
    char tmp[size];
    memcpy(tmp, a, size);
    memcpy(a, b, size);
    memcpy(b, tmp, size);
}

// 通用冒泡排序
void generic_bubble_sort(void *base, size_t n, size_t size,
                         int (*cmp)(const void *, const void *)) {
    char *arr = (char *)base;
    for (size_t i = 0; i < n - 1; i++) {
        for (size_t j = 0; j < n - 1 - i; j++) {
            void *p = arr + j * size;
            void *q = arr + (j + 1) * size;
            if (cmp(p, q) > 0) {
                swap_bytes(p, q, size);
            }
        }
    }
}

// 比较函数示例：比较两个整数
int cmp_int(const void *a, const void *b) {
    return *(int *)a - *(int *)b;
}

int main() {
    int a[] = {34, 12, 56, 78, 23, 9};
    int n = sizeof(a) / sizeof(a[0]);
    generic_bubble_sort(a, n, sizeof(int), cmp_int);
    for (int i = 0; i < n; i++) {
        printf("%d ", a[i]);
    }
    return 0;
}

这里的关键是 void * 指针和 size 参数。我们把数组当成连续的字节块，通过 char * 指针按字节移动。比较函数由调用者提供，交换函数按字节复制。

我在一个项目里用这个模式写过排序模块，支持 int、float、结构体（按某个字段排序）。调用方只需要注册自己的比较函数，代码量减少了一半以上。

四、知识体系总览

下面这张图帮你理清本章的核心逻辑：指针如何贯穿排序的各个环节。

从这张图可以看得很清楚：冒泡和快排是“术”，指针操作是“器”，回调函数是“道”。三者结合，你就能写出既高效又通用的排序代码。

好了，这一章的内容就到这里。指针与排序的结合，说白了就是让你从“会用数组”进阶到“理解内存”。下一章我们会继续深入指针的高级应用，敬请期待。

---

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