[DataStructure]Selection Sort(選擇排序法)

選擇排序法的複雜度為O(n^2)，和氣泡排序法是一樣的

他的步驟是將要排序的數字分為未排序和已排序兩部份

接著在未排序找出最小值插入已排序的末端

以{123456,123,12,33,44,55}為例

未排序
123456 123 12 33 44 55
找到最小值12，並與第一筆123456交換(12是已排序的數字了)
[12] 123 123456 33 44 55
找到最小值33，並與第一筆123交換
[12 33] 123456 123 44 55
找到最小值44，並與第一筆123456交換
[12 33 44] 123 123456 55
找到最小值55，並與第一筆123交換
[12 33 44 55] 123456 123
找到最小值123，並與第一筆123456交換
[12 33 44 55 123] 123456
完成
[12 33 44 55 123 123456]

Java

public class test{
	static int [] num = {123456,123,12,33,44,55};
	public static void main(String [] argv){
		selection_sort();
		for(int i : num){
			System.out.print(i + " ");
		}
	}
	//選擇排序法
	public static void selection_sort(){
		for(int i = 0; i < num.length - 1; i++) { 
            int m = i; 
            //找出最小值
            for(int j = i + 1; j < num.length; j++){
            	if(num[j] < num[m]) m = j; 
            }
            //與最前面一筆(未排序)的交換
            if(i != m){
            	int temp = num[i];
            	num[i] = num[m];
            	num[m] = temp;
            }
        }
	}
}