【正确答案】正确答案：数组A的相邻两段分别有序，要求将两段合并为一段有序。由于要求附加空间为O(1)，所以将两段最后一个元素比较，若正序，则后段指针前移；若逆序则交换，并调整前段有序。重复以上过程直到正序为止。最佳情况出现在数组第二段值最小元素A[n一k+1]大于等于第一段值最大元素A[n一k]，只比较k次无须交换，时间复杂度为O(n)。最差情况出现在第一段的最小值大干第二段的最大值，两段数据间发生了k次交换，而且每次段交换都在段内发生了平均(k-1)次交换，时间复杂度为O(n ² )。