NOC創新編程復賽題——選擇排序算法

白二娃

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

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

要求：1.當前省份與面積是一一對應的，使用選擇排序算法完成面積數據排序，并保持省份與面積的對應關系。

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

這道題指定了必須用選擇排序算法。在編程學習中一般我們會學習8種排序算法。這幾種排序的關系和特點如圖。

選擇排序是一種非常直觀的排序算法。首先在未排序列表中找到最小（或最大）元素，存放到排序序列的起始位置。然后，再從剩余未排序元素中繼續尋找最小（或最大）元素。以此類推，直到所有元素均排序完成。

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

題目中已經給出兩個列表“面積”和“省份”，每個表格34個數據。我們循環比較面積列表中第min項（當前最小項）和第i項（m項后的某一項）的大小，并換位，最終就能將面積最小的放到第1位。