1528 問題 E: 藍(lán)橋杯算法提高VIP-插入排序
時(shí)間限制: 1s
內(nèi)存限制: 128MB 提交: 1550 解決: 322
題目描述
排序，顧名思義，是將若干個(gè)元素按其大小關(guān)系排出一個(gè)順序。形式化描述如下：有n個(gè)元素a[1]，a[2]，…，a[n]，從小到大排序就是將它們排成一個(gè)新順序a[i[1]]< a[i[2]]< …< a[i[n]]
i[k]為這個(gè)新順序。
插入排序，顧名思義，是通過插入操作完成排序。其直覺和方法來源于打牌時(shí)安排牌的方法。每次摸起一張牌，你都會(huì)將其插入到現(xiàn)在手牌中它按順序應(yīng)在的那個(gè)位置。插入排序每一步都類似這個(gè)摸牌過程。比如現(xiàn)在有整數(shù)數(shù)組：{3, 1, 5, 4, 2}
第一步：插入3 得到新序列{3}
第二步：插入1 得到新序列{1 3}
第三步：插入5 得到新序列{1 3 5}
第四步：插入4 得到新序列{1 3 4 5}
第五步：插入2 得到新序列{1 2 3 4 5}
為了看程序中如何完成插入過程，我們以第五步為例：
初始時(shí)：1 3 4 5 2
將2存入臨時(shí)變量tmp
將下標(biāo)j指向2之前的元素5，然后根據(jù)tmp和a[j]的大小關(guān)系決定該元素是否應(yīng)該后移。如果a[j]> tmp，則將a[j]后移到a[j+1]，序列變成1 3 4 5 5。
將下標(biāo)j前移
判斷a[j]> tmp，后移a[j]到a[j+1]，得到1 3 4 4 5
將下標(biāo)j前移
判斷a[j]> tmp，后移a[j]到a[j+1]，得到1 3 3 4 5
因?yàn)閍[j]< =tmp，所以將tmp放回a[j+1]，得到 1 2 3 4 5
現(xiàn)在，輸入n個(gè)整數(shù)，根據(jù)以上算法，輸出插入排序的全過程。
輸入
第一行一個(gè)正整數(shù)n，表示元素個(gè)數(shù)
第二行為n個(gè)整數(shù)，以空格隔開
數(shù)據(jù)規(guī)模和約定
n< =100
整數(shù)元素在int范圍內(nèi)
輸出
有n個(gè)元素，因此輸出部分分為n個(gè)部分，每個(gè)部分開頭行為：Insert element[i]，i為第幾個(gè)元素。然后對于每一個(gè)部分，輸出該部分該元素在插入排序過程中的每一步產(chǎn)生的新序列，初始時(shí)的序列以Init:打頭，然 后每一步后移數(shù)組元素后的元素序列以Move back:打頭，最后得到的最終結(jié)果序列以Final:打頭。序列元素間以一個(gè)空格隔開。示例請看樣例輸出。每一個(gè)部分的Insert element[i]之后的每一步的輸出行之前要縮進(jìn)兩格，即輸出兩個(gè)空格。
樣例輸出
Insert element[1]:
Init:3
Final:3
Insert element[2]:
Init:3 1
Move back:3 3
Final:1 3
Insert element[3]:
Init:1 3 5
Final:1 3 5
Insert element[4]:
Init:1 3 5 4
Move back:1 3 5 5
Final:1 3 4 5
Insert element[5]:
Init:1 3 4 5 2
Move back:1 3 4 5 5
Move back:1 3 4 4 5
Move back:1 3 3 4 5
Final:1 2 3 4 5
提示
零基礎(chǔ)同學(xué)可以先學(xué)習(xí)
視頻課程，包含C/C++、Python、百練、藍(lán)橋杯輔導(dǎo)、算法數(shù)據(jù)結(jié)構(gòu)等課程，提供視頻講解以及配套習(xí)題，還有老師答疑，
點(diǎn)擊這里了解課程詳情