數據結構考研分類復習真題 第五章 答案[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)

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

From:http://tw.wingwit.com/Article/program/sjjg/201311/23028.html