参考答案

正确答案：void adjust(int A[]int n)／／数组A[n一2k+1．．n—k]和[n—k+1．．n]中元素分别升序算法使A[n一2k+1．．n]升序{i=n—k；j=n—k+1；while(A[i]>A[j]){x=A[i]；A[i]=A[j]；／／值小者左移值大者暂存于xk=j+1；while(k<n&&x>A[k])A[k一1]=A[k++]；／／调整后段有序A[k一1]=x；i一一；j一一；／／修改前段最后元素和后段第一元素的指针}}／／算法结束
此问题考查的知识点是合并两个有序序列。题目中数组A的相邻两段分别有序，要求将两段合并为一段有序。由于要求附加空间复杂度为D(1)，所以将前段最后一个元素与后段第一个元素比较，若正序，则算法结束；若逆序则交换，并将前段的最后一个元素插入到后段中，使后段有序。重复以上过程直到正序为止。最佳情况出现在数组第二段[n一k+1．．n]中值最小元素A[n一k+1]大于等于第一段值最大元素A[n一k]，只比较一次无须交换。最差情况出现在第一段的最小值大于第二段的最大值，两段数据间发生了k次交换，而且每次段交换都在段内发生了平均(k一1)次交换，时间复杂度为O(n)。