一、算法描述

1.首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置
2.再從剩余未排序元素中繼續(xù)尋找最?。ù螅┰?，然后放到已排序序列的末尾。
3.重復第二步，直到所有元素均排序完畢。

二、算法性能

時間復雜度

選擇排序的交換操作介于 0 和 (n - 1)次之間。選擇排序的比較操作為 n (n - 1） / 2 次之間。選擇排序的賦值操作介于 0 和 3 (n - 1） 次之間。比較次數O(n^2），比較次數與關鍵字的初始狀態(tài)無關，總的比較次數N=(n-1）+(n-2）+...+1=n*(n-1）/2。交換次數O(n），最好情況是，已經有序，交換0次；最壞情況交換n-1次，逆序交換n/2次。交換次數比冒泡排序少多了，由于交換所需CPU時間比比較所需的CPU時間多，n值較小時，選擇排序比冒泡排序快

算法穩(wěn)定性

選擇排序是給每個位置選擇當前元素最小的，比如給第一個位置選擇最小的，在剩余元素里面給第二個元素選擇第二小的，依次類推，直到第n-1個元素，第n個元素不用選擇了，因為只剩下它一個最大的元素了。那么，在一趟選擇，如果一個元素比當前元素小，而該小的元素又出現在一個和當前元素相等的元素后面，那么交換后穩(wěn)定性就被破壞了。舉個例子，序列5 8 5 2 9，我們知道第一遍選擇第1個元素5會和2交換，那么原序列中兩個5的相對前后順序就被破壞了，所以選擇排序是一個不穩(wěn)定的排序算法

三、具體代碼

public class SelectionSort implements IArraySort {

    @Override
    public int[] sort(int[] sourceArray) throws Exception {
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
        // 總共要經過 N-1 輪比較
        for (int i = 0; i < arr.length - 1; i++) {
            int min = i;
            // 每輪需要比較的次數 N-i
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < arr[min]) {
                    // 記錄目前能找到的最小值元素的下標
                    min = j;
                }
            }

            // 將找到的最小值和i位置所在的值進行交換
            if (i != min) {
                int tmp = arr[i];
                arr[i] = arr[min];
                arr[min] = tmp;
            }
        }
        return arr;
    }
}