演算法類型
貪婪演算法, 排序演算法演算法目的
藉由比較key value來將資料做排序
演算法描述
selection sort的精神是將資料切成兩部份，一部份爲已排序另一部份則是尚未排序，並且每次於尚未排序的資料堆中找出key value最小的資料放入已排序資料堆中的最後一個位置。舉例來說，有個數列如下:
現在此數列所有的數字都在未排序的資料堆裡，我們可以由左至右對數列做一次掃描，找出最小的數字1，並且將它與數列的第一個數字3做交換，這樣我們就可以把1歸納在已排序的資料堆裡，如下圖:
接著繼續從剩下未排序的資料堆裡，找出最小的數字3，並且將它與未排序資料堆的第一個數字5做交換，這樣就可以讓3被歸納在已排序的資料堆裡，如下圖:
再繼續從剩下未排序的資料堆裡，找出最小的數字4，並且將它與未排序資料堆的第一個數字9做交換，這樣就可以讓4被歸納在已排序的資料堆裡，如下圖:
依此類推，不斷地重複這些步驟就可以把全部的資料都排序好了。
第一次掃描找到最小值的比較次數: n - 1次
第二次掃描找到最小值的比較次數: n - 2次
第三次掃描找到最小值的比較次數: n - 3次
...
第n次掃描找到最小值的比較次數: 0次
總共比較次數: (0 + n - 1) * n / 2 = (n ^ 2 - n) / 2
故此演算法屬於O(n ^ 2)
C
Java
Python
現在此數列所有的數字都在未排序的資料堆裡，我們可以由左至右對數列做一次掃描，找出最小的數字1，並且將它與數列的第一個數字3做交換，這樣我們就可以把1歸納在已排序的資料堆裡，如下圖:
接著繼續從剩下未排序的資料堆裡，找出最小的數字3，並且將它與未排序資料堆的第一個數字5做交換，這樣就可以讓3被歸納在已排序的資料堆裡，如下圖:
再繼續從剩下未排序的資料堆裡，找出最小的數字4，並且將它與未排序資料堆的第一個數字9做交換，這樣就可以讓4被歸納在已排序的資料堆裡，如下圖:
依此類推，不斷地重複這些步驟就可以把全部的資料都排序好了。
效率分析
設總資料量爲n, 分析單位爲比較次數第一次掃描找到最小值的比較次數: n - 1次
第二次掃描找到最小值的比較次數: n - 2次
第三次掃描找到最小值的比較次數: n - 3次
...
第n次掃描找到最小值的比較次數: 0次
總共比較次數: (0 + n - 1) * n / 2 = (n ^ 2 - n) / 2
故此演算法屬於O(n ^ 2)
程式實作
C
#include <stdio.h>
void selSort(int *, int);
int main() {
int arr[8] = {3, 5, 9, 10, 8, 1, 12, 4};
int dataNum = 8;
int i;
printf("before sorting: ");
for (i=0; i<dataNum; i++)
printf("%d ", arr[i]);
printf("\n");
selSort(arr, dataNum);
printf("after sorting: ");
for (i=0; i<dataNum; i++)
printf("%d ", arr[i]);
printf("\n");
return 0;
}
void selSort(int *arr, int dataNum) {
int i, j;
for (i=0; i<dataNum; i++) {
int smallestIndex = i;
for (j=i+1; j<dataNum; j++) {
if (arr[smallestIndex] > arr[j])
smallestIndex = j;
}
if (smallestIndex != i) {
int temp = arr[smallestIndex];
arr[smallestIndex] = arr[i];
arr[i] = temp;
}
}
}
Java
public class SelSort {
public static void main(String[] args) {
int[] arr = {3, 5, 9, 10, 8, 1, 12, 4};
System.out.print("before sorting: ");
for (int num: arr)
System.out.printf("%d ", num);
System.out.println();
selSort(arr);
System.out.print("after sorting: ");
for (int num: arr)
System.out.printf("%d ", num);
System.out.println();
}
private static void selSort(int[] arr) {
for (int i=0; i<arr.length; i++) {
int smallestIndex = i;
for (int j=i+1; j<arr.length; j++) {
if (arr[smallestIndex] > arr[j])
smallestIndex = j;
}
if (smallestIndex != i) {
int temp = arr[smallestIndex];
arr[smallestIndex] = arr[i];
arr[i] = temp;
}
}
}
}
Python
def selSort(arr):
for i in range(len(arr)):
smallestIndex = i
for j in range(i + 1, len(arr)):
if arr[smallestIndex] > arr[j]:
smallestIndex = j
if smallestIndex != i:
temp = arr[smallestIndex]
arr[smallestIndex] = arr[i]
arr[i] = temp
arr = [3, 5, 9, 10, 8, 1, 12, 4]
print "before sorting:",
for num in arr:
print num,
print ""
selSort(arr)
print "after sorting:",
for num in arr:
print num,
print ""
![\begin{figure}
\centering
\setlength{\unitlength}{0.0125in} %
\begin{picture}
(2...
...raisebox{0pt}[0pt][0pt]{$\bullet
\bullet \bullet$ }}}
\end{picture}
\end{figure}](http://uva.onlinejudge.org/external/1/101img2.gif)
where n is the number of blocks) should appear followed immediately by a colon. If there is at least a block on it, the colon must be followed by one space, followed by a list of blocks that appear stacked in that position with each block number separated from other block numbers by a space. Don't put any trailing spaces on a line.