递归实现数组排序判断函数的优化方案咨询

问题背景 #

需要判断整数数组属于三类：严格递增排序（每个元素均大于前一个，如[1,2,3,4,5]）、非严格递增排序（整体递增，允许连续相同值，如[1,3,3,5]）、完全无序（如[4,2,1]）。现有递归实现的findIfArrayIsSorted函数，希望从可读性与性能层面进行优化。

原核心递归函数代码：

int findIfArrayIsSorted(int array[], int size, int *precision)
{
    if (size > 1)
    {
        if (array[size-1] < array[size-2])
        {
            *precision = 0;
            return 0;
        }
        else if (array[size-1] == array[size-2])
        {
            *precision = 0;
            return findIfArrayIsSorted(array, size - 1, precision);
        }
        else if (array[size-1] > array[size-2])
            return findIfArrayIsSorted(array, size - 1, precision);
    }
    return 1;
}

可读性优化 #

• 调整遍历逻辑：原函数从数组末尾向前比较，改为从起始位置向后遍历，用索引i对比array[i]与array[i+1]，符合常规阅读习惯，避免size-1这类易混淆的索引计算。
• 优化变量命名：将precision改为is_strict，直接表达“是否严格递增”的含义，消除歧义。
• 简化条件分支：合并冗余判断，减少嵌套层级，让逻辑流程更直观。
• 添加清晰注释：在关键节点标注逻辑意图，降低理解成本。

性能优化 #

• 提前终止逻辑：一旦发现逆序元素，立即返回无序结果，避免不必要的递归调用。
• 尾递归改造：将递归调用改为函数最后一步操作，部分编译器可将其优化为循环，减少栈帧开销，降低栈溢出风险。
• 迭代替代递归：对于极大数组，递归存在栈溢出隐患，迭代实现性能更稳定，且无递归栈开销。

优化后的递归实现 #

// 递归判断数组排序类型
// 返回值：1表示有序（严格/非严格），0表示无序
// is_strict：输出参数，1表示严格递增，0表示非严格递增（仅当返回1时有效）
int findIfArrayIsSorted(int array[], int size, int *is_strict) {
    // 终止条件：长度<=1的数组默认严格有序
    if (size <= 1) {
        return 1;
    }

    int prev = array[size - 2];
    int curr = array[size - 1];

    if (curr < prev) {
        // 发现逆序，标记为无序
        *is_strict = 0;
        return 0;
    } else if (curr == prev) {
        // 存在相等元素，标记为非严格递增后递归判断剩余部分
        *is_strict = 0;
        return findIfArrayIsSorted(array, size - 1, is_strict);
    } else {
        // 当前元素递增，保持is_strict状态递归判断剩余部分
        return findIfArrayIsSorted(array, size - 1, is_strict);
    }
}

性能优先的迭代实现 #

如果需要避免栈溢出风险或追求极致性能，推荐使用迭代版本：

// 迭代判断数组排序类型
// 返回值：1表示有序（严格/非严格），0表示无序
// is_strict：输出参数，1表示严格递增，0表示非严格递增（仅当返回1时有效）
int findIfArrayIsSortedIterative(int array[], int size, int *is_strict) {
    if (size <= 1) {
        *is_strict = 1;
        return 1;
    }

    *is_strict = 1; // 默认假设严格递增
    for (int i = 0; i < size - 1; i++) {
        if (array[i + 1] < array[i]) {
            // 发现逆序，直接返回无序
            *is_strict = 0;
            return 0;
        } else if (array[i + 1] == array[i]) {
            // 存在相等元素，修正为非严格递增
            *is_strict = 0;
        }
    }
    return 1;
}

使用说明 #

调用逻辑保持原有习惯：初始化is_strict为1，传入函数后根据返回值和is_strict的取值判断结果：

• 返回1且is_strict=1：严格递增排序
• 返回1且is_strict=0：非严格递增排序
• 返回0：完全无序

内容的提问来源于stack exchange，提问作者MrSigma123