链表归并排序代码中如何统计交换（逆序）次数与比较次数

我编写了用于链表的归并排序代码，想要统计排序过程中的交换（逆序，inversions）次数与比较次数，但不清楚比较计数器和交换计数器应该放在Merge合并函数还是MergeSort排序主函数中，也不知道具体要放在函数的哪个位置。我的代码如下：

Merge合并函数原代码 #

node* Merge(node* h1, node* h2, int &comp, int &swaps){ 
    node *t1 = new node; 
    node *t2 = new node; 
    node *temp = new node;

    // Return if the first list is empty.
    if(h1 == NULL)
        return h2;

    // Return if the Second list is empty.
    if(h2 == NULL)
        return h1;

    t1 = h1;

    // A loop to traverse the second list, to merge the nodes to h1 in sorted way.
    while (h2 != NULL)
    {
        // Taking head node of second list as t2.
        t2 = h2;

        // Shifting second list head to the next.
        h2 = h2->next;
        t2->next = NULL;

        // If the data value is lesser than the head of first list add that node at the beginning.
        comp++;
        if(h1->data > t2->data)
        {
            t2->next = h1;
            h1 = t2;
            t1 = h1;
            continue;
        }

        // Traverse the first list.
        flag:
        if(t1->next == NULL)
        {
            t1->next = t2;
            t1 = t1->next;
        }
        // Traverse first list until t2->data more than node's data.
        else if((t1->next)->data <= t2->data)
        {
            t1 = t1->next;
            goto flag;
        }
        else
        {
            // Insert the node as t2->data is lesser than the next node.
            temp = t1->next;
            t1->next = t2;
            t2->next = temp;
        }
    }

    // Return the head of new sorted list.
    return h1;
}

MergeSort主函数原代码 #

void MergeSort(node **head, int &comp, int &swaps)
{
    node *first = new node;
    node *second = new node;
    node *temp = new node;
    first = *head;
    temp = *head;

    // Return if list have less than two nodes.
    if(first == NULL || first->next == NULL)
    {
        return;
    }
    else
    {
        // Break the list into two half as first and second as head of list.
        while(first->next != NULL)
        {
            first = first->next;
            if(first->next != NULL)
            {
                temp = temp->next;
                first = first->next;
            }
        }
        second = temp->next;
        temp->next = NULL;
        first = *head;
    }

    // Implementing divide and conquer approach.
    MergeSort(&first, comp, swaps);
    MergeSort(&second, comp, swaps);

    // Merge the two part of the list into a sorted one.      
    *head = Merge(first, second, comp, swaps);
}

计数放置方案 #

• 比较计数器、逆序计数器全部放在Merge函数中即可，MergeSort仅做分治拆分，没有元素对比和逆序产生，不需要加任何计数逻辑。
• 现有代码的比较计数已经覆盖了t2和h1头结点对比的场景，但漏了遍历第一个子链表时的每次对比计数，需要补上。
• 逆序计数的逻辑是：只要第二个子链表的元素小于第一个子链表当前及之后的元素，累加第一个子链表剩余元素的数量即可，这部分逻辑放在插入节点的分支前即可。

修正后的Merge函数核心片段 #

// 对比h1头结点和t2的大小，这是1次比较，原有计数正确
comp++;
if(h1->data > t2->data)
{
    // 新增逆序计数：h1开头的所有剩余节点都和t2构成逆序对
    int first_remain = 0;
    node *cnt = h1;
    while(cnt) {
        first_remain++;
        cnt = cnt->next;
    }
    swaps += first_remain;

    t2->next = h1;
    h1 = t2;
    t1 = h1;
    continue;
}

// Traverse the first list.
flag:
if(t1->next == NULL)
{
    t1->next = t2;
    t1 = t1->next;
}
else {
    // 新增比较计数：每次判断t2和t1后续节点大小都算1次比较
    comp++;
    if((t1->next)->data <= t2->data)
    {
        t1 = t1->next;
        goto flag;
    }
    else
    {
        // 新增逆序计数：t1之后的所有剩余节点都和t2构成逆序对
        int first_remain = 0;
        node *cnt = t1->next;
        while(cnt) {
            first_remain++;
            cnt = cnt->next;
        }
        swaps += first_remain;

        temp = t1->next;
        t1->next = t2;
        t2->next = temp;
    }
}

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