NOC創(chuàng)新編程復(fù)賽題——選擇排序算法

白二娃

本題來自NOC創(chuàng)新編程復(fù)賽題中的第四題，這是一道算法編程題，考查的是選擇排序算法。題目原文：

我國幅員遼闊，國土面積在全世界排名第三，其中各省、自治區(qū)、直轄市面積均存放于列表中，每個(gè)省級(jí)區(qū)域的面積各不相同，請(qǐng)把它們按照面積從小到大的順序排列。

要求：1.當(dāng)前省份與面積是一一對(duì)應(yīng)的，使用選擇排序算法完成面積數(shù)據(jù)排序，并保持省份與面積的對(duì)應(yīng)關(guān)系。

2. 完成排序后，角色說出“我的家鄉(xiāng)是XXX，它的面積全國排名第X”。

這道題指定了必須用選擇排序算法。在編程學(xué)習(xí)中一般我們會(huì)學(xué)習(xí)8種排序算法。這幾種排序的關(guān)系和特點(diǎn)如圖。

選擇排序是一種非常直觀的排序算法。首先在未排序列表中找到最?。ɑ蜃畲螅┰?，存放到排序序列的起始位置。然后，再從剩余未排序元素中繼續(xù)尋找最?。ɑ蜃畲螅┰亍Ｒ源祟愅?，直到所有元素均排序完成。

比如數(shù)據(jù)[2，5，1，7，6]用選擇算法從小到大排序，2和5比較，2是最小值;最小值2繼續(xù)和1比較，1成為最小值;最小值1再依次和7、6比較，1都是最小值;因此2和1交換位置。第一輪結(jié)束數(shù)據(jù)為[1，5，2，7，6]。第二輪結(jié)束數(shù)據(jù)為[1，2，5，7，6]，最小值2和未排序首數(shù)字5交換位置（1已經(jīng)完成排序不再考慮）。最終排序結(jié)果為[1，2，5，6，7]。

題目中已經(jīng)給出兩個(gè)列表“面積”和“省份”，每個(gè)表格34個(gè)數(shù)據(jù)。我們循環(huán)比較面積列表中第min項(xiàng)（當(dāng)前最小項(xiàng)）和第i項(xiàng)（m項(xiàng)后的某一項(xiàng)）的大小，并換位，最終就能將面積最小的放到第1位。