鏁版嵁緇撴瀯絎簲绔犵畻娉曡璁￠[15]_璺ㄨ€冪綉

1. 璁炬暟緇?/span>A[1..n]涓紝A[n-2k+1..n-k]鍜?/span>[n-k+1..n]涓厓绱犲悇鑷粠灝忓埌澶ф帓濂藉簭錛岃瘯璁捐涓€涓畻娉曚嬌A[n-2k+1..n]鎸変粠灝忓埌澶ф搴忔帓濂藉簭銆傚茍鍒嗘瀽綆楁硶鎵€闇€鐨勮綆楁椂闂淬€傘€?a target="_blank">紱忓窞澶у 1998 鍥涖€?/span>3 (10鍒?/span>)銆?/span>

銆€銆€銆愬弬鑰冪瓟妗堛€?/span>

銆€銆€[棰樼洰鍒嗘瀽]鏈涓暟緇?/span>A鐨勭浉閭諱袱孌靛垎鍒湁搴忥紝瑕佹眰灝嗕袱孌靛悎騫朵負涓€孌墊湁搴忋€傜敱浜庤姹傞檮鍔犵┖闂翠負O(1),鎵€浠ュ皢鍓嶆鏈€鍚庝竴涓厓绱犱笌鍚庢絎竴涓厓绱犳瘮杈冿紝鑻ユ搴忥紝鍒欑畻娉曠粨鏉燂紱鑻ラ€嗗簭鍒欎氦鎹紝騫跺皢鍓嶆鐨勬渶鍚庝竴涓厓绱犳彃鍏ュ埌鍚庢涓紝浣垮悗孌墊湁搴忋€傞噸澶嶄互涓婅繃紼嬬洿鍒版搴忎負姝€?/span>

銆€銆€void adjust(int A[],int n)

銆€銆€//鏁扮粍A[n-2k+1..n-k]鍜?/span>[n-k+1..n]涓厓绱犲垎鍒崌搴忥紝綆楁硶浣?/span>A[n-2k+1..n]鍗囧簭

銆€銆€{i=n-k;j=n-k+1;

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

銆€銆€{x=A[i]; A[i]=A[j]; //鍊煎皬鑰呭乏縐伙紝鍊煎ぇ鑰呮殏瀛樹簬x

銆€銆€k=j+1;

銆€銆€while (k<n && x>A[k]) A[k-1]=A[k++]; //璋冩暣鍚庢鏈夊簭

銆€銆€A[k-1]=x;

銆€銆€i--; j--; //淇敼鍓嶆鏈€鍚庡厓绱犲拰鍚庢絎竴鍏冪礌鐨勬寚閽?/span>

銆€銆€}

銆€銆€}綆楁硶緇撴潫

銆€銆€[綆楁硶璁ㄨ]鏈€浣蟲儏鍐靛嚭鐜板湪鏁扮粍絎簩孌?/span>[n-k+1..n]涓€兼渶灝忓厓绱?/span>A[n-k+1]澶т簬絳変簬絎竴孌靛€兼渶澶у厓绱?/span>A[n-k]錛屽彧姣旇緝涓€嬈℃棤欏諱氦鎹€傛渶宸儏鍐靛嚭鐜板湪絎竴孌電殑鏈€灝忓€煎ぇ浜庣浜屾鐨勬渶澶у€鹼紝涓ゆ鏁版嵁闂村彂鐢熶簡k嬈′氦鎹紝鑰屼笖姣忔孌典氦鎹㈤兘鍦ㄦ鍐呭彂鐢熶簡騫沖潎錛?/span>k-1錛夋浜ゆ崲錛屾椂闂村鏉傚害涓?/span>O(n2)銆?/span>