内部排序算法：直接選擇排序

基本思想

n個記錄的檔案的直接選擇排序可經過n-1趟直接選擇排序得到有序結果：

初始狀态：無序區為r[1..n]，有序區為空。

第1趟排序：在無序區r[1..n]中選出關鍵字最小的記錄r[k]，将它與無序區的第1個記錄r[1] 交換，使r[1..1]和r[2..n]分别變為記錄個數增加1個的新有序區和記錄個數減少1個的新無序區。

……

第i趟排序：第i趟排序開始時，目前有序區和無序區分别為r[1..i-1]和r[i..n](1≤i≤n-1)。 該趟排序從目前無序區中選出關鍵字最小的記錄r[k]，将它與無序區的第1個記錄r[i]交換，使r[1..i] 和r[i+1..n]分别變為記錄個數增加1個的新有序區和記錄個數減少1個的新無序區。

這樣，n個記錄的檔案的直接選擇排序可經過n-1趟直接選擇排序得到有序結果。

算法實作

直接選擇排序算法，java實作，代碼如下所示：

<code>01</code>

<code>public</code> <code>abstract</code> <code>class</code> <code>sorter {</code>

<code>02</code>

<code></code><code>public</code> <code>abstract</code> <code>void</code> <code>sort(</code><code>int</code><code>[] array);</code>

<code>03</code>

<code>}</code>

<code>04</code>

<code>05</code>

<code>public</code> <code>class</code> <code>straightselectionsorter</code><code>extends</code> <code>sorter {</code>

<code>06</code>

<code>07</code>

<code></code><code>@override</code>

<code>08</code>

<code></code><code>public</code> <code>void</code> <code>sort(</code><code>int</code><code>[] array) {</code>

<code>09</code>

<code></code><code>int</code> <code>tmp;</code><code>// 用于交換資料的暫存單元</code>

<code>10</code>

<code></code><code>for</code> <code>(</code><code>int</code> <code>i =</code><code>0</code><code>; i &lt; array.length -</code><code>1</code><code>; i++) {</code><code>// 這裡隻要從0~array.length-2即可</code>

<code>11</code>

<code></code><code>int</code> <code>k = i;</code>

<code>12</code>

<code></code><code>for</code> <code>(</code><code>int</code> <code>j = i +</code><code>1</code><code>; j &lt; array.length; j++) {</code><code>// 該循環可以找到右側無序區最小的元素array[k]</code>

<code>13</code>

<code></code><code>if</code> <code>(array[k] &gt; array[j]) {</code>

<code>14</code>

<code></code><code>k = j;</code>

<code>15</code>

<code></code><code>}</code>

<code>16</code>

<code>17</code>

<code></code><code>if</code> <code>(k != i) {</code><code>// 如果array[i]不是無序區最小的，需要與無序區最小的進行交換</code>

<code>18</code>

<code></code><code>tmp = array[i];</code>

<code>19</code>

<code></code><code>array[i] = array[k];</code>

<code>20</code>

<code></code><code>array[k] = tmp;</code>

<code>21</code>

<code>22</code>

<code></code><code>// 如果array[i]是無序區最小的元素，不需要執行交換</code>

<code>23</code>

<code>24</code>

<code>25</code>

直接選擇排序算法，python實作，代碼如下所示：

<code>class</code> <code>sorter:</code>

<code></code><code>'''</code>

<code></code><code>abstract sorter class, which provides shared methods being used by</code>

<code></code><code>subclasses.</code>

<code></code><code>__metaclass__</code><code>=</code> <code>abcmeta</code>

<code></code>

<code></code><code>@abstractmethod</code>

<code></code><code>def</code> <code>sort(</code><code>self</code><code>, array):</code>

<code></code><code>pass</code>

<code>class</code> <code>straightselectionsort(sorter):</code>

<code></code><code>straight selection sorter</code>

<code></code><code>i</code><code>=</code> <code>0</code>

<code></code><code>length</code><code>=</code> <code>len</code><code>(array)</code>

<code></code><code>while</code> <code>i&lt;length</code><code>-</code><code>1</code><code>:</code>

<code></code><code>k</code><code>=</code> <code>i</code>

<code></code><code>j</code><code>=</code> <code>i</code>

<code></code><code>while</code> <code>j&lt;length:</code>

<code></code><code>if</code> <code>array[j]&lt;array[k]:</code>

<code></code><code>k</code><code>=</code> <code>j</code>

<code></code><code>j</code><code>=</code> <code>j</code><code>+</code> <code>1</code>

<code>26</code>

<code></code><code>if</code> <code>k!</code><code>=</code><code>i:</code>

<code>27</code>

<code></code><code>array[k], array[i]</code><code>=</code> <code>array[i], array[k]</code>

<code>28</code>

<code></code><code>i</code><code>=</code> <code>i</code><code>+</code> <code>1</code>

排序過程

首先，從0~n-1個元素中找到最小的元素，交換到0位置上；

其次，再從1~n-1中找到次最小的元素，交換到1位置上；

……；

最後從n-2~n-1中找到最小的元素，交換到n-2位置上。n-1位置上一定是最大的元素，是以總共進行n-1趟選擇排序。

需要注意的是：

每次确定無序區後，其中除了第一個元素之外的其它元素（設為e）與第一個元素（設為e）比較，隻有滿足e&lt;e的時候才需要交換一次。

排序過程示例如下：

假設待排序數組為array = {94,12,34,76,26,9,0,37,55,76,37,5,68,83,90,37,12,65,76,49}，數組大小為20。

第1趟選擇排序

從array[1,n-1]中找到最小的元素：

array[0] = 94&gt;array[1] = 12，交換array[0]與array[1]，即array[0] = 12array[2] = 34不成立，不交換；

array[0] = 12&gt;array[3] = 76不成立，不交換；

array[0] = 12&gt;array[4] = 26不成立，不交換；

array[0] = 12&gt;array[5] = 9，交換array[0]與array[5]，即array[0] = 9array[6] = 0，交換array[0]與array[6]，即array[0] = 0array[7] = 37不成立，不交換；

array[0] = 0&gt;array[8] = 55不成立，不交換；

array[0] = 0&gt;array[9] = 76不成立，不交換；

array[0] = 0&gt;array[10] = 37不成立，不交換；

array[0] = 0&gt;array[11] = 5不成立，不交換；

array[0] = 0&gt;array[12] = 68不成立，不交換；

array[0] = 0&gt;array[13] = 83不成立，不交換；

array[0] = 0&gt;array[14] = 90不成立，不交換；

array[0] = 0&gt;array[15] = 37不成立，不交換；

array[0] = 0&gt;array[16] = 12不成立，不交換；

array[0] = 0&gt;array[17] = 65不成立，不交換；

array[0] = 0&gt;array[18] = 76不成立，不交換；

array[0] = 0&gt;array[19] = 49不成立，不交換。

此時數組狀态如下：{0,94,34,76,26,12,9,37,55,76,37,5,68,83,90,37,12,65,76,49}。

此時，有序區為{0}，無序區為{94,34,76,26,12,9,37,55,76,37,5,68,83,90,37,12,65,76,49}。

第2趟選擇排序

從array[2,n-1]中找到最小的元素：

array[1] = 94&gt;array[2] = 34，交換array[1]與array[2]，即array[1] = 34array[3] = 76不成立，不交換；

array[1] = 34&gt;array[4] = 26，交換array[1]與array[4]，即array[1] = 26array[5] = 12，交換array[1]與array[5]，即array[1] = 12array[6] = 9，交換array[1]與array[6]，即array[1] = 9array[7] = 37不成立，不交換；

array[1] = 0&gt;array[8] = 55不成立，不交換；

array[1] = 0&gt;array[9] = 76不成立，不交換；

array[1] = 0&gt;array[10] = 37不成立，不交換；

array[1] = 9&gt;array[11] = 5，交換array[1]與array[11]，即array[1] = 5array[12] = 68不成立，不交換；

array[1] = 5&gt;array[13] = 83不成立，不交換；

array[1] = 5&gt;array[14] = 90不成立，不交換；

array[1] = 5&gt;array[15] = 37不成立，不交換；

array[1] = 5&gt;array[16] = 12不成立，不交換；

array[1] = 5&gt;array[17] = 65不成立，不交換；

array[1] = 5&gt;array[18] = 76不成立，不交換；

array[1] = 5&gt;array[19] = 49不成立，不交換。

此時數組狀态如下：{0,5,94,76,34,26,12,37,55,76,37,9,68,83,90,37,12,65,76,49}。

此時，有序區為{0,5}，無序區為{94,76,34,26,12,37,55,76,37,9,68,83,90,37,12,65,76,49}。

第3趟選擇排序

排序後數組狀态為：{0,5,9,94,76,34,26,37,55,76,37,12,68,83,90,37,12,65,76,49}。

此時，有序區為{0,5,9}，無序區為{94,76,34,26,37,55,76,37,12,68,83,90,37,12,65,76,49}。

第4趟選擇排序

排序後數組狀态變化：

{0,5,9,76,94,34,26,37,55,76,37,12,68,83,90,37,12,65,76,49}，

{0,5,9,34,94,76,26,37,55,76,37,12,68,83,90,37,12,65,76,49}，

{0,5,9,26,94,76,34,37,55,76,37,12,68,83,90,37,12,65,76,49}，

{0,5,9,12,94,76,34,37,55,76,37,26,68,83,90,37,12,65,76,49}，

此時，有序區為{0,5,9,12}，無序區為{94,76,34,37,55,76,37,26,68,83,90,37,12,65,76,49}。

第n-1趟選擇排序

依此類推，執行n-1趟選擇排序，最後得到：有序區為{0,5,9,12,12,26,34,37,37,37,49,55,65,68,76,76,76,83,90}，無序區為{94}，此時整個數組已經有序，n-1趟選擇排序後，排序完成。

算法分析

時間複雜度

記錄比較次數：

無論待排序數組初始狀态如何，都要進行n-1趟選擇排序：

第1趟：比較n-1次；

第2趟：比較n-2次；

第n-1趟：比較1次。

進而，總共的比較次數為：1+2+……+(n-1) = n(n-1)/2

記錄移動次數：

如果待排序數組為正序，則記錄不需要交換，記錄移動次數為0；

如果當排序數組為逆序，則：

第1趟：交換1次，移動3次；

第2趟：交換1次，移動3次；

第n-1趟：交換1次，移動3次。

進而，總共的移動次數為：3(n-1) = 3(n-1)。

是以，時間複雜度為o(n2)。

空間複雜度

在選擇排序的過程中，設定一個變量用來交換元素，是以空間複雜度為o(1)。

排序穩定性

選擇排序是就地排序。

通過上面的排序過程中數組的狀态變化可以看出：直接選擇排序是不穩定的。