快速排隊(duì)怎么做？

逸之

今天天朗氣清，正是適合戶外活動的好日子。同學(xué)們在操場上以班級為單位，排成了一排排整齊的隊(duì)伍，等待老師的安排。

老師滿意地點(diǎn)點(diǎn)頭，說：“同學(xué)們，今天我們來做個(gè)小游戲?！彼f完就給同學(xué)們貼上了臂貼。“剛才給大家貼上的是印有1～10000范圍內(nèi)的100個(gè)隨機(jī)整數(shù)的臂貼，大家該如何用最快的速度，按從小到大的順序重新排隊(duì)呢？”老師貼完問同學(xué)們。

插入排隊(duì)

同學(xué)們愣了一會兒，1位編號較小的同學(xué)趕緊報(bào)出自己的號碼，很快就有不少人擠到了他的前面。

此時(shí)，三班的班長小顧站了出來，說：“大家安靜，我是621號。同學(xué)們從隊(duì)首開始一個(gè)個(gè)地過來，比我大的站我后面，比我小的站我前面。后來的同學(xué)從新隊(duì)伍的隊(duì)首往隊(duì)尾走，依次對比雙方的臂貼數(shù)字，主動插在比自己小和比自己大的兩個(gè)人中間?！?/p>

同學(xué)們在小顧的引導(dǎo)下，就像玩撲克牌時(shí)抓牌的過程一樣，每抓一張牌就把它插在正確的位置，同學(xué)們又重新排成了整齊的隊(duì)伍。

冒泡排隊(duì)

“同學(xué)們再想想，還有沒有其他的方法？”老師一邊提問，一邊給同學(xué)們更換印有新編號的臂章。

新的一輪游戲開始了。盲目報(bào)數(shù)只會讓現(xiàn)場更加混亂，同學(xué)們吸取了上一輪的經(jīng)驗(yàn)，整個(gè)隊(duì)伍變得十分安靜。

這時(shí)，二班的小沈同學(xué)突然想到：既然每個(gè)人都可以看到自己前后同學(xué)的編號，那他就可以讓編號更小的同學(xué)走到前面。整個(gè)隊(duì)伍只需要按一定次序去做，就能通過兩兩比較、兩兩交換的方式把擁有最小編號的同學(xué)送到隊(duì)首。

首先，讓隊(duì)尾的最后2位同學(xué)比較編號的大小，如果第100位的編號比第99位的編號小，他倆就交換，反之就不動。接著，讓第99位和第98位比較編號的大小，同樣把編號小的同學(xué)換到第98位，以此類推，直到隊(duì)首的第2位和第1位同學(xué)完成比較，隊(duì)伍中編號最小的同學(xué)就站到了第1位。但這樣也只選出了第1個(gè)編號的同學(xué)，要將隊(duì)伍排好將會是個(gè)大工程?。⌒∩蛐⌒囊硪淼匕炎约旱南敕ǜ嬖V了老師。

排序前：

隊(duì)伍從后往前比較編號：

編號最小的同學(xué)來到了第1位：

老師朝她豎起了大拇指，并向同學(xué)們轉(zhuǎn)述了這一方法：“每一輪比較中，編號小的同學(xué)就像水底的氣泡慢慢地冒了上來，這種方法就叫‘冒泡排隊(duì)吧！”同學(xué)們哈哈大笑，花了好一陣工夫，終于把每個(gè)“氣泡”都“冒”到了正確的位置。

快速排隊(duì)

看著所剩不多的活動時(shí)間，老師決定不再為難大家，公布了最后一種方法——“快速排隊(duì)”。

老師開始介紹：“首先，我讓編號為2021的小張作為第1條界線?，F(xiàn)在編號比小張小的同學(xué)都排到他前面，編號比他大的同學(xué)都排到他后面，順序不重要。”所有的同學(xué)都動了起來，很快站成了一個(gè)新的隊(duì)伍。

“大家有沒有發(fā)現(xiàn)，以小張為分界線，同學(xué)們已經(jīng)分成了2組。接下來小張不要?jiǎng)?，新分出來的組重復(fù)剛才的過程，各選出1名同學(xué)當(dāng)分界線后繼續(xù)分組，這樣整個(gè)隊(duì)伍就能繼續(xù)分成4組、8組、16組……組的數(shù)量像細(xì)胞分裂一樣暴增，很快就能完成整體的排隊(duì)。這樣，所有尚未處在正確位置的同學(xué)自始至終沒有閑著，排隊(duì)的效率一下就變高了！”

同學(xué)們張大嘴巴，對這種獨(dú)特的排隊(duì)方式感到無比新奇。大家在熱鬧卻不混亂的氛圍中，真的以更快的速度完成了排隊(duì)。

平時(shí)大家排隊(duì)集合的時(shí)候是不是也亂糟糟的呢？那還不快來學(xué)兩招，到時(shí)候看看哪個(gè)班級的隊(duì)伍排得又快又好！