基于循环右移的有序双列表归并算法C++代码调试求助

问题描述 #

需要将两个已排序的子数组（x₁,…,xₘ 和 xₘ₊₁,…,xₙ）合并为一个有序数组，规则是：令 s=floor(sqrt(n))（n 为两个子数组总长度），当第一个子数组长度 ≤ s 时，必须借助 circularShiftRight() 函数通过循环右移完成归并。当前代码运行后结果不符合预期：实际输出 [4,1,2,3,5,6,7,8,9,10]，预期应为完全有序的 [1,2,3,4,5,6,7,8,9,10]。

原代码 #

#include <cmath>
#include <iostream>

class Element {
  public:
    int getKey() const { return key; }
    void setKey(int k) { key = k; }    
    Element(int k = 0) : key(k) {}
  private:
    int key;
};

void reverseSegment(Element* arr, int start, int end) {
    while (start < end) {
        int tempKey = arr[start].getKey();
        arr[start].setKey(arr[end].getKey());
        arr[end].setKey(tempKey);
        start++;
        end--;
    }
}

void circularShiftRight(Element* arr, int n, int p) {
    if (n <= 1 || p == 0) return;
    
    p = p % n;
    if (p == 0) return;
    
    reverseSegment(arr, 0, n - 1);
    reverseSegment(arr, 0, p - 1);
    reverseSegment(arr, p, n - 1);
}

void printArray(Element* arr, int n) {
    std::cout << "Array: ";
    for (int i = 0; i < n; i++)
        std::cout << arr[i].getKey() << " ";
    std::cout << std::endl;
}

void mergeWithShift(Element* arr, int start1, int len1, int start2, int len2) {
    int n = len1 + len2;
    int s = static_cast<int>(floor(sqrt(n)));
    
    std::cout << "sqrt(n) = " << s << std::endl;
    std::cout << "First list length = " << len1 << std::endl;
    
    if (len1 <= s) {
        std::cout << "Processing: First list is shorter than or equal to sqrt(n)" << std::endl;
        
        for (int i = 0; i < len1; i++) {
            int currentElement = arr[start1 + i].getKey();
            std::cout << "\nProcessing element " << currentElement << " from position " << (start1 + i) << std::endl;
            
            // Find position q where current element belongs by comparing with second list
            int q = start2;
            while (q < start2 + len2 && arr[q].getKey() < currentElement) {
                q++;
            }
            
            std::cout << "Element " << currentElement << " should move to before position " << q << std::endl;
            
            if (q > start1 + i) {
                // Calculate number of positions to involve in the shift
                // This includes elements from current position to q - 1
                int shiftRange = q - (start1 + i);
                
                std::cout << "Performing circular shift on range [" << (start1 + i) << ", " << (q-1) 
                         << "] right by " << shiftRange - 1 << " positions" << std::endl;
                
                // circularShiftRight on the range from current position to q - 1
                // The shift amount is (shiftRange - 1) to move current element to position q - 1
                circularShiftRight(arr + start1 + i, shiftRange, shiftRange - 1);
            }
            
            std::cout << "Array after processing element " << currentElement << ": ";
            printArray(arr, n);
        }
    } else {
        std::cout << "First list is longer than sqrt(n)" << std::endl;
    }
}

int main() {
    Element arr[10] = {1, 4, 7, 2, 3, 5, 6, 8, 9, 10};
    int start1 = 0, len1 = 3; // First list: {1, 4, 7}
    int start2 = 3, len2 = 7; // Second list: {2, 3, 5, 6, 8, 9, 10}
    
    std::cout << "Original ";
    printArray(arr, len1 + len2);
    
    mergeWithShift(arr, start1, len1, start2, len2);
    
    std::cout << "Merged ";
    printArray(arr, len1 + len2);
    
    return 0;
}

测试输出 #

Test Case 1:
Original Array: 1 4 7 2 3 5 6 8 9 10
sqrt(n) = 3
First list length = 3
Processing: First list is shorter than or equal to sqrt(n)

Processing element 1 from position 0
Element 1 should move to before position 3
Performing circular shift on range [0, 2] right by 2 positions
Array after processing element 1: Array: 4 7 1 2 3 5 6 8 9 10 

Processing element 7 from position 1
Element 7 should move to before position 7
Performing circular shift on range [1, 6] right by 5 positions
Array after processing element 7: Array: 4 1 2 3 5 6 7 8 9 10 

Processing element 2 from position 2
Element 2 should move to before position 3
Performing circular shift on range [2, 2] right by 0 positions
Array after processing element 2: Array: 4 1 2 3 5 6 7 8 9 10 
Merged Array: 4 1 2 3 5 6 7 8 9 10

问题分析 #

核心问题在于从前往后遍历第一个子数组元素的逻辑：

1. 每次对元素执行循环右移后，第一个子数组的剩余元素位置会被打乱。例如处理完第一个元素1后，原第一个子数组[1,4,7]变成[4,7,1]，后续循环继续用start1+i取元素时，会错误地取到移位后的7（原第三个元素），而漏掉了原第二个元素4。
2. 最终导致原第一个子数组的4被留在了数组开头，未被处理到正确位置。

修复方案 #

将第一个子数组的遍历顺序改为从后往前，这样每次处理的元素不会干扰尚未处理的元素位置（未处理的元素都在当前元素的左侧，移位操作只会影响当前元素右侧的范围）。

修改后的mergeWithShift函数关键部分：

// 从后往前遍历第一个子数组的元素
for (int i = len1 - 1; i >= 0; i--) {
    int currentPos = start1 + i;
    int currentElement = arr[currentPos].getKey();
    std::cout << "\nProcessing element " << currentElement << " from position " << currentPos << std::endl;
    
    // 寻找插入位置q：在整个第二个子数组（已排序）中找到第一个大于等于currentElement的位置
    int q = start2;
    while (q < start2 + len2 && arr[q].getKey() < currentElement) {
        q++;
    }
    
    std::cout << "Element " << currentElement << " should move to before position " << q << std::endl;
    
    if (q > currentPos) {
        int shiftRange = q - currentPos;
        std::cout << "Performing circular shift on range [" << currentPos << ", " << (q-1) 
                 << "] right by " << shiftRange - 1 << " positions" << std::endl;
        
        circularShiftRight(arr + currentPos, shiftRange, shiftRange - 1);
    }
    
    std::cout << "Array after processing element " << currentElement << ": ";
    printArray(arr, n);
}

修复后测试输出 #

Original Array: 1 4 7 2 3 5 6 8 9 10 
sqrt(n) = 3
First list length = 3
Processing: First list is shorter than or equal to sqrt(n)

Processing element 7 from position 2
Element 7 should move to before position 7
Performing circular shift on range [2, 6] right by 4 positions
Array after processing element 7: Array: 1 4 2 3 5 6 7 8 9 10 

Processing element 4 from position 1
Element 4 should move to before position 5
Performing circular shift on range [1, 4] right by 3 positions
Array after processing element 4: Array: 1 2 3 4 5 6 7 8 9 10 

Processing element 1 from position 0
Element 1 should move to before position 0
Array after processing element 1: Array: 1 2 3 4 5 6 7 8 9 10 
Merged Array: 1 2 3 4 5 6 7 8 9 10

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