C语言 归并排序的基本操作是什么，我如何在最好的情况下找到基本步骤的递归关系

Question

我正在分析C编程中的归并排序，我不明白算法的basic operation将是什么，以及我如何为基本步骤设置和recurrence relation(最佳情况)!

我认为基本操作将是comparison step，已被评论为基本操作。如果是，那么我如何设置和recurrence relation的这一步?

#include <stdio.h>
// lets take a[5] = { 32, 45, 67, 2, 7 } as the array to be sorted.
// merge sort function
void mergeSort(int a[], int p, int r)
{
int q;
if (p < r)
{
q = (p + r) / 2;
mergeSort(a, p, q);
mergeSort(a, q + 1, r);
merge(a, p, q, r);
}
}
// function to merge the subarrays
void merge(int a[], int p, int q, int r)
{
int b[5];   //same size of a[]
int i, j, k;
k = 0;
i = p;
j = q + 1;
while (i <= q && j <= r)
{
if (a[i] < a[j])  //basic operation
{
b[k++] = a[i++];    // same as b[k]=a[i]; k++; i++;
}
else
{
b[k++] = a[j++];
}
}

while (i <= q)
{
b[k++] = a[i++];
}

while (j <= r)
{
b[k++] = a[j++];
}

for (i = r; i >= p; i--)
{
a[i] = b[--k];  // copying back the sorted list to a[]
} 
}

Answer 1

由于上面的答案提供了流程的代码，所以我只是针对一般类型的问题解决相同问题背后的思考过程。这是一个分而治之的经典例子。这类问题的复杂性分析依赖于识别这3个操作的复杂性

1. 划分:这是您将问题划分为子问题所做的工作量。在归并排序的情况下，这是将数组划分为2个长度相等的子数组的步骤。这一步的复杂性将是O(1)，因为它涉及到找到数组的中点。
2. Conquer:此步骤将涉及解决上述步骤产生的子问题。这里的子问题是排序两个大小为原始大小一半的数组。
3. Combine:这一步涉及到组合子问题的结果来找到原始问题的结果，在这种情况下，这将减少到从两个排序的子数组中创建一个排序数组的问题，这就是合并函数所做的。这一步的复杂度将与段的大小成线性关系。

所以如果T(n))是大小为n的数组排序的复杂度。，T (n/2)排序大小为n/2的段的复杂度． 现在，如果我要用前面提到的3个步骤来表达复杂性，它看起来就像

T O (n) = (1) + 2 * T (n/2) + O (n)

可以用大师定理求解，复杂度为O(nlog(n))

Answer 2

几点提示:

• 递归关系(不存在于你的片段)是:
  1. 排序左半部分
  2. 对右半部分排序
  3. 合并两半。
• 决定传递哪些参数，或者中点和总大小，或者左大小和右大小。
• 决定尺寸是否包含最终元素
• 对于大小和索引更倾向于使用无符号数据类型;
• merge()函数只需要三个参数;递归调用不需要传递指向数组第一个元素的指针，但可以在数组的某个位置给出一个指针。
• 你不需要数组的完整副本，你只需要它的一半。

---

void merge(int array[], unsigned lsiz, unsigned rsiz)
{
unsigned lpos, rpos, totpos, totsiz;
int *spare;
if (lsiz > 1) { // recurse: sort the left side
unsigned half;
half = lsiz /2;
merge(array, half, lsiz - half);
}
if (rsiz > 1) { // recurse: sort the right side
unsigned half;
half = rsiz /2;
merge(array+lsiz, half, rsiz - half);
}
/*
** allocate a copy of the left side
** , so that we can merge *in place*
*/
spare = malloc(sizeof *array * lsiz);
if (!spare) return;
memcpy(spare, array, sizeof *spare *lsiz);
totsiz = lsiz + rsiz;
lpos = 0;
rpos = lsiz;
#if 0
for (totpos = 0; lpos < lsiz && rpos < totsiz; totpos++) {
if (spare[lpos] <= array[rpos]) { array[totpos] = spare[lpos++];}
else { array[totpos] = array[rpos++]; }
}
while (lpos < lsiz)  {array[totpos++] = spare[lpos++]; }
while (rpos < totsiz) {array[totpos++] = array[rpos++]; }
#else
for (totpos = 0; totpos < totsiz; totpos++) {
if (lpos >= lsiz) goto right;
if (rpos >= totsiz) goto left;
if (spare[lpos] > array[rpos]) goto right;
left:
array[totpos] = spare[lpos++];
continue;
right:
array[totpos] = array[rpos++];
continue;
}
#endif
free(spare);
}

---

注意:我保留了goto版本，因为我认为它实际上更具可读性。