数据结构考研分类复习真题 第五章 答案[46]

[题目分析]本题中数组A的相邻两段分别有序要求将两段合并为一段有序由于要求附加空间为O()所以将前段最后一个元素与后段第一个元素比较若正序则算法结束若逆序则交换并将前段的最后一个元素插入到后段中使后段有序重复以上过程直到正序为止

void adjust(int A[]int n)

//数组A[nk+nk]和[nk+n]中元素分别升序算法使A[nk+n]升序

{i=nk;j=nk+;

while(A[i]>A[j])

{x=A[i]; A[i]=A[j]; //值小者左移值大者暂存于x

k=j+;

while (k<n && x>A[k]) A[k]=A[k++]; //调整后段有序

A[k]=x;

i; j; //修改前段最后元素和后段第一元素的指针

}

}算法结束

[算法讨论]最佳情况出现在数组第二段[nk+n]中值最小元素A[nk+]大于等于第一段值最大元素A[nk]只比较一次无须交换最差情况出现在第一段的最小值大于第二段的最大值两段数据间发生了k次交换而且每次段交换都在段内发生了平均（k）次交换时间复杂度为O(n)

[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []