面试题：C语言插入排序的优化

Question

请用C语言实现插入排序，并思考如何对其进行优化以减少比较次数，比如在部分有序数组场景下的优化。请给出优化前后的代码，并简要说明优化思路。

Answer 1

插入排序原始代码

#include <stdio.h>

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

        // 将大于key的元素向后移动一个位置
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
}

优化思路

在部分有序数组场景下，可以使用二分查找来确定插入位置，从而减少比较次数。因为对于部分有序数组，已经排序的部分是有序的，适合二分查找。

优化后代码

#include <stdio.h>
#include <stdlib.h>

// 二分查找函数，返回插入位置
int binarySearch(int arr[], int low, int high, int key) {
    while (low <= high) {
        int mid = low + (high - low) / 2;

        if (arr[mid] == key)
            return mid + 1;
        else if (arr[mid] < key)
            low = mid + 1;
        else
            high = mid - 1;
    }
    return low;
}

void insertionSortOptimized(int arr[], int n) {
    int i, key, j, insertIndex;
    for (i = 1; i < n; i++) {
        key = arr[i];
        j = i - 1;

        insertIndex = binarySearch(arr, 0, j, key);

        // 移动元素
        while (j >= insertIndex) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
}

总结

原始的插入排序在每一步将一个新元素插入到已排序部分的合适位置时，通过线性比较来确定位置。而优化后的版本，在部分有序数组场景下，利用二分查找确定插入位置，减少了比较次数，提高了效率。