常见的排序方法笔试题解析

冒泡排序：最基础的考察点

面试中经常出现冒泡排序的实现，虽然效率不高，但逻辑清晰，适合判断编程基本功。比如有道题是：写一个函数将数组 [64, 34, 25, 12, 22, 11, 90] 按升序排列。

void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

很多人能写出来，但容易忽略内层循环的边界优化，导致多跑几轮。

快速排序：高频必考题

快排几乎是大厂笔试标配。题目常要求手撕代码，并分析时间复杂度。比如给定一个乱序整数数组，用快排完成排序。

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 - 1; j++) {
        if (arr[j] < pivot) {
            i++;
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    int temp = arr[i + 1];
    arr[i + 1] = arr[high];
    arr[high] = temp;
    return i + 1;
}

写的时候最容易出错的是索引越界和递归边界处理，尤其是分区点选得不好时，性能会退化到 O(n²)。

归并排序：稳定排序的代表

有些岗位特别看重稳定性，比如需要保持相等元素的原始顺序，这时候归并排序就派上用场了。常见题目是实现一个稳定的排序算法来处理学生成绩单，相同分数的学生按输入顺序排列。

void mergeSort(int arr[], int l, int r) {
    if (l < r) {
        int m = l + (r - l) / 2;
        mergeSort(arr, l, m);
        mergeSort(arr, m + 1, r);
        merge(arr, l, m, r);
    }
}

归并的核心在于合并两个有序数组，空间复杂度是 O(n)，虽然费内存，但胜在稳定可靠。

选择排序与插入排序：对比题常客

笔试里也喜欢让比较几种简单排序的区别。比如问：“插入排序在什么情况下比快排更快？” 答案其实是当数据量小且基本有序时，插入排序的实际运行速度反而更优。

插入排序的代码简洁：

void insertionSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

它像打扑克理牌一样，每次拿一张新牌插进前面合适的位置。

堆排序：理解难度稍高

堆排序考得不如前几个多，但在一些系统级开发岗位中会出现。题目可能是“不用额外空间对数组排序”，这时堆排的优势就出来了。

核心是构建最大堆，然后逐个把堆顶元素移到末尾。代码实现要注意左右子节点的下标计算：

void heapify(int arr[], int n, int i) {
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;

    if (left < n && arr[left] > arr[largest])
        largest = left;

    if (right < n && arr[right] > arr[largest])
        largest = right;

    if (largest != i) {
        int temp = arr[i];
        arr[i] = arr[largest];
        arr[largest] = temp;
        heapify(arr, n, largest);
    }
}

写完别忘了主函数要从最后一个非叶子节点开始向下调整。