这是我的合并排序代码：这是合并功能
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;
}
这是调用merge函数的merge排序函数。我不知道我应该把比较和交换计数器放在merge还是merge排序中，我也不知道把它们放在函数的哪里。
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);
}
我不确定将交换和比较计数器放在哪里，以计算合并排序进行的交换和比较的数量？
对于比较，您可以为每个比较增加一个计数器。
在泡沫排序的情况下，交换的数量与反转的数量相同，但合并排序不进行交换，所以需要的是反转的数量。
反转是数组[i]>array[j]和i<j、 在数组中。例如：
int InversionCount(int array[], int n)
{
int count = 0;
for (int i = 0; i < n - 1; i++)
for (int j = i + 1; j < n; j++)
if (array[i] > array[j])
count++;
return count;
}
一个典型的合并步骤合并两个已经排序的子数组，array[低到中1]，array[中到端1]。设i＝到左数组的索引(从低到中1(，j＝到右数组(从中到端1(。如果在合并过程中遇到array[i]>array[j]，则array[i到mid-1]都将大于array[j]。看看你是否可以用这个来确定和求和合并排序的合并步骤部分的反转次数
要根据问题中的代码对链表执行此操作，请进行以下更改，以跟踪每个子列表中的节点数量：
node * MergeSortR(node *head, int count, int &comp, int &swaps);
node *MergeSort(node *head, int &comp, int &swaps)
{
node * ptr = head;
int count = 0;
comp = 0;
swaps = 0;
while(ptr != NULL){
count++;
ptr = ptr->next;
}
if(count < 2)
return head;
return MergeSortR(head, count, comp, swaps);
}
node * MergeSortR(node *first, int count, int &comp, int &swaps)
{
if(count < 2)
return first;
node * second = first;
int fstcnt = count/2;
int sndcnt = count - fstcnt;
for(int i = 1; i < fstcnt; i++)
second = second->next;
node *temp = second;
second = second->next;
temp->next = NULL;
first = MergeSortR(first, fstcnt, comp, swaps);
second = MergeSortR(second, sndcnt, comp, swaps);
return Merge(first, fstcnt, second, sndcnt, comp, swaps);
}
n个元素的最坏情况(反向排序的元素(反转计数为n(n-1(/2。如果使用带符号的32位整数进行反转计数，则最大列表大小限制为65536，以避免任何溢出的机会。