逸之



今天天朗氣清,正是適合戶外活動(dòng)的好日子。同學(xué)們?cè)诓賵?chǎng)上以班級(jí)為單位,排成了一排排整齊的隊(duì)伍,等待老師的安排。
老師滿意地點(diǎn)點(diǎn)頭,說:“同學(xué)們,今天我們來做個(gè)小游戲。”她說完就給同學(xué)們貼上了臂貼。“剛才給大家貼上的是印有1~10000范圍內(nèi)的100個(gè)隨機(jī)整數(shù)的臂貼,大家該如何用最快的速度,按從小到大的順序重新排隊(duì)呢?”老師貼完問同學(xué)們。
插入排隊(duì)
同學(xué)們愣了一會(huì)兒,1位編號(hào)較小的同學(xué)趕緊報(bào)出自己的號(hào)碼,很快就有不少人擠到了他的前面。
此時(shí),三班的班長(zhǎng)小顧站了出來,說:“大家安靜,我是621號(hào)。同學(xué)們從隊(duì)首開始一個(gè)個(gè)地過來,比我大的站我后面,比我小的站我前面。后來的同學(xué)從新隊(duì)伍的隊(duì)首往隊(duì)尾走,依次對(duì)比雙方的臂貼數(shù)字,主動(dòng)插在比自己小和比自己大的兩個(gè)人中間。”
同學(xué)們?cè)谛☆櫟囊龑?dǎo)下,就像玩撲克牌時(shí)抓牌的過程一樣,每抓一張牌就把它插在正確的位置,同學(xué)們又重新排成了整齊的隊(duì)伍。
冒泡排隊(duì)
“同學(xué)們?cè)傧胂耄€有沒有其他的方法?”老師一邊提問,一邊給同學(xué)們更換印有新編號(hào)的臂章。
新的一輪游戲開始了。盲目報(bào)數(shù)只會(huì)讓現(xiàn)場(chǎng)更加混亂,同學(xué)們吸取了上一輪的經(jīng)驗(yàn),整個(gè)隊(duì)伍變得十分安靜。
這時(shí),二班的小沈同學(xué)突然想到:既然每個(gè)人都可以看到自己前后同學(xué)的編號(hào),那他就可以讓編號(hào)更小的同學(xué)走到前面。整個(gè)隊(duì)伍只需要按一定次序去做,就能通過兩兩比較、兩兩交換的方式把擁有最小編號(hào)的同學(xué)送到隊(duì)首。……