排序方法笔试题常见考点解析

找工作面试时，排序算法几乎是计算机相关岗位绕不开的坎。尤其是数据库开发、后端工程师这类职位，笔试里总爱考排序方法。别看这些算法课本上都学过，真到写代码或者分析复杂度的时候，不少人还是容易栽跟头。

为什么排序算法总被拿来出题

数据库底层大量依赖排序操作，比如 ORDER BY 的实现、索引构建、归并连接等。企业想招能写高效代码的人，自然要看看你对基础算法的理解够不够深。一个简单的冒泡排序，可能背后考察的是你对时间换空间、稳定性、原地排序这些概念的掌握。

高频排序算法题型盘点

快排手写几乎是标配。面试官不会直接让你背代码，但会让你在白板或在线编辑器里实现分区逻辑。比如给个数组 [3, 1, 4, 1, 5, 9, 2]，要求用快速排序从小到大排好。这时候不光要写对，还得注意边界条件处理，比如左右指针相遇的情况。

void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

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

归并排序也常考，特别是和链表结合。比如“如何对单链表进行稳定排序”，标准答案就是自底向上的归并。堆排序虽然写起来麻烦点，但考察堆结构理解很合适，像“用堆实现 Top K 问题”就是变形题。

稳定性与应用场景挂钩

数据库里特别看重排序的稳定性。比如你按成绩排序后，相同成绩的学生还能保持原来输入的顺序，这就是稳定排序的好处。归并和插入排序是稳定的，快排默认不是，这点在答题时得说清楚。有次笔试题问“ORDER BY 多字段时该用哪种排序”，其实就是在考稳定性的实际意义。

时间复杂度不能死记硬背

看到题目先想数据规模。小数组插排可能比快排还快，因为常数低；大数据量就得上 O(n log n) 的算法。还有种题是“几乎有序的数组怎么排最快”，答案通常是插入排序，因为它对近似有序的数据响应特别好。

有时候题目会限定条件，比如“只能用 O(1) 额外空间”，这就排除了归并（需要辅助数组），得选快排或堆排。要是再加一句“必须稳定”，那可就难了，得动脑筋想想有没有折中办法。

实际笔试中的坑

有人写完代码一提交，测试用例全挂。一看才发现是整型溢出——比较时直接写 a - b > 0，结果遇到负数炸了。正确做法是用 if(a > b) 判断。还有人忘了递归终止条件，导致栈溢出。这些细节在平时练习时就得养成习惯。

另外别忽视非比较排序。虽然数据库里用得少，但笔试偶尔会考。比如“已知数据范围在 1 到 100 之间，怎么 O(n) 排好序”，桶排序或计数排序就能派上用场。这种题考的是思维灵活性。