算法编程题：复杂度、排序与解题方法（6 题）

解题思路： 复制输入，从左到右把当前元素插入已经有序的前缀。

不变量： 每轮开始时 [0, i) 已按升序稳定排列。

public static class AlgCode001Solution
{
    public static int[] Solve(int[] numbers)
    {
        int[] result = (int[])numbers.Clone();
        for (int index = 1; index < result.Length; index++)
        {
            int value = result[index];
            int position = index - 1;
            while (position >= 0 && result[position] > value)
            {
                result[position + 1] = result[position];
                position--;
            }
            result[position + 1] = value;
        }
        return result;
    }
}

复杂度： 最坏时间 O(n²)，最好时间 O(n)，额外空间 O(n)。

边界用例： 空数组；已经有序；全部相等。

面试追问：

• 如果允许原地修改输入，空间复杂度如何变化？

解题思路： 递归排序左右区间，再把两个有序区间稳定合并。

不变量： 合并时临时数组始终包含两个输入前缀中最小的若干元素。

public static class AlgCode002Solution
{
    public static int[] Solve(int[] numbers)
    {
        int[] result = (int[])numbers.Clone();
        int[] buffer = new int[result.Length];
        Sort(result, buffer, 0, result.Length);
        return result;
    }
    
    private static void Sort(int[] values, int[] buffer, int start, int end)
    {
        if (end - start <= 1) return;
        int middle = start + (end - start) / 2;
        Sort(values, buffer, start, middle);
        Sort(values, buffer, middle, end);
        int left = start, right = middle, write = start;
        while (left < middle || right < end)
        {
            if (right >= end || (left < middle && values[left] <= values[right]))
                buffer[write++] = values[left++];
            else
                buffer[write++] = values[right++];
        }
        Array.Copy(buffer, start, values, start, end - start);
    }
}

复杂度： 时间 O(n log n)，额外空间 O(n)，递归栈 O(log n)。

边界用例： 空数组；单元素；重复值；极端有序输入。

面试追问：

• 链表归并排序为什么可以把额外数组空间降下来？

解题思路： 把区间划分为小于、等于和大于基准值的三段。

不变量： 扫描过程中左段小于基准，中段等于基准，右段大于基准。

public static class AlgCode003Solution
{
    public static int[] Solve(int[] numbers)
    {
        int[] result = (int[])numbers.Clone();
        Sort(result, 0, result.Length - 1);
        return result;
    }
    
    private static void Sort(int[] values, int left, int right)
    {
        if (left >= right) return;
        int pivot = values[left + (right - left) / 2];
        int lower = left, index = left, upper = right;
        while (index <= upper)
        {
            if (values[index] < pivot)
                (values[lower++], values[index++]) = (values[index], values[lower]);
            else if (values[index] > pivot)
                (values[index], values[upper--]) = (values[upper], values[index]);
            else
                index++;
        }
        Sort(values, left, lower - 1);
        Sort(values, upper + 1, right);
    }
}

复杂度： 平均时间 O(n log n)，最坏时间 O(n²)，递归栈平均 O(log n)。

边界用例： 空数组；全部相等；已经有序；大量重复值。

面试追问：

• 如何随机选择基准以降低持续遇到坏划分的概率？

解题思路： 按起点排序，当前区间与结果末尾重叠时扩展终点。

不变量： 结果中的区间互不重叠，且覆盖所有已扫描输入。

public static class AlgCode004Solution
{
    public static int[][] Solve(int[][] intervals)
    {
        if (intervals.Length == 0) return [];
        int[][] sorted = intervals
            .Select(interval => new[] { interval[0], interval[1] })
            .OrderBy(interval => interval[0])
            .ThenBy(interval => interval[1])
            .ToArray();
        var merged = new List<int[]> { sorted[0] };
        for (int index = 1; index < sorted.Length; index++)
        {
            int[] last = merged[^1];
            int[] current = sorted[index];
            if (current[0] <= last[1])
                last[1] = Math.Max(last[1], current[1]);
            else
                merged.Add(current);
        }
        return merged.ToArray();
    }
}

复杂度： 排序时间 O(n log n)，扫描 O(n)，额外空间 O(n)。

边界用例： 空输入；相邻端点；完全包含；负数端点。

面试追问：

• 如果输入已经按起点排序，可以省掉哪部分成本？

解题思路： 记录原始下标，以主键和原始下标组成排序键。

不变量： 相同 Priority 的记录始终按原始下标递增。

public static class AlgCode005Solution
{
    public static (string Name, int Priority)[] Solve(
        (string Name, int Priority)[] items)
    {
        return items
            .Select((item, index) => (item, index))
            .OrderBy(entry => entry.item.Priority)
            .ThenBy(entry => entry.index)
            .Select(entry => entry.item)
            .ToArray();
    }
}

复杂度： 时间 O(n log n)，额外空间 O(n)。

边界用例： 空输入；全部主键相同；名称重复。

面试追问：

• 如果排序 API 已承诺稳定，还需要显式保存原始下标吗？

解题思路： 归并左右有序段；右侧元素先写入时，一次贡献左侧剩余数量。

不变量： 递归返回前区间已经有序，计数包含区间内部全部逆序对。

public static class AlgCode006Solution
{
    public static long Solve(int[] numbers)
    {
        int[] values = (int[])numbers.Clone();
        int[] buffer = new int[values.Length];
        return Count(values, buffer, 0, values.Length);
    }
    
    private static long Count(int[] values, int[] buffer, int start, int end)
    {
        if (end - start <= 1) return 0;
        int middle = start + (end - start) / 2;
        long count = Count(values, buffer, start, middle) +
            Count(values, buffer, middle, end);
        int left = start, right = middle, write = start;
        while (left < middle || right < end)
        {
            if (right >= end || (left < middle && values[left] <= values[right]))
                buffer[write++] = values[left++];
            else
            {
                buffer[write++] = values[right++];
                count += middle - left;
            }
        }
        Array.Copy(buffer, start, values, start, end - start);
        return count;
    }
}

复杂度： 时间 O(n log n)，额外空间 O(n)，结果使用 long 防止计数溢出。

边界用例： 空数组；重复值不构成逆序；完全逆序；计数超过 int。

面试追问：

• 为什么相等值不能计入逆序对？