如何非递归实现O(1)空间、nlogn时间的模k数组排序

要同时满足O(n log n)时间复杂度、O(1)额外空间、纯迭代无递归、不创建新数组的要求，选择迭代实现的堆排序作为核心算法，仅需自定义比较规则为「按元素对k取模的结果升序排列」即可，完全匹配所有约束。

• 比较规则自定义：两个元素排序优先级完全由num % k的计算结果决定，模值更小的元素靠前排列，模值相等时无稳定性要求。
• 迭代式建堆：从最后一个非叶子节点开始倒序遍历，通过循环下沉调整节点位置，构建基于模值比较的大顶堆，全程无递归。
• 迭代式排序：循环将堆顶（当前未排序区间内模值最大的元素）与未排序区间的末尾元素交换，缩小未排序区间范围，再通过循环下沉调整新堆顶恢复大顶堆性质，直到未排序区间长度为1即完成排序。
• 空间控制：全程仅使用固定数量的临时变量存储索引、交换临时值，不创建任何长度与输入相关的数组、集合对象，无递归产生的栈空间开销。

public static void sortMod(int [] a, int k) {
    int len = a.length;
    if (len <= 1 || k == 0) {
        return;
    }

    // 迭代构建基于模k值比较的大顶堆
    for (int i = len / 2 - 1; i >= 0; i--) {
        int current = i;
        while (current < len) {
            int left = 2 * current + 1;
            int right = 2 * current + 2;
            int largest = current;

            if (left < len && (a[left] % k) > (a[largest] % k)) {
                largest = left;
            }
            if (right < len && (a[right] % k) > (a[largest] % k)) {
                largest = right;
            }

            if (largest != current) {
                int temp = a[current];
                a[current] = a[largest];
                a[largest] = temp;
                current = largest;
            } else {
                break;
            }
        }
    }

    // 迭代完成排序
    for (int i = len - 1; i > 0; i--) {
        // 堆顶元素交换到已排序区间头部
        int temp = a[0];
        a[0] = a[i];
        a[i] = temp;

        // 迭代调整剩余未排序区间为大顶堆
        int current = 0;
        int heapLen = i;
        while (current < heapLen) {
            int left = 2 * current + 1;
            int right = 2 * current + 2;
            int largest = current;

            if (left < heapLen && (a[left] % k) > (a[largest] % k)) {
                largest = left;
            }
            if (right < heapLen && (a[right] % k) > (a[largest] % k)) {
                largest = right;
            }

            if (largest != current) {
                int swapTemp = a[current];
                a[current] = a[largest];
                a[largest] = swapTemp;
                current = largest;
            } else {
                break;
            }
        }
    }
}

• 时间复杂度：建堆耗时O(n)，排序阶段共执行n-1次堆调整，单次调整耗时O(log n)，总时间复杂度稳定为O(n log n)，无最坏情况退化问题。
• 空间复杂度：仅使用固定个数的int临时变量，未创建任何新数组、集合对象，无递归栈开销，额外空间复杂度为O(1)。
• 实现形式：所有调整、遍历逻辑全部通过for、while循环实现，无任何递归调用，符合纯迭代要求。
• 边界处理：已覆盖数组长度小于等于1、k为0的异常边界场景，不会抛出运行时错误。

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