Sort-Selection Sort 选择排序

排序算法之选择排序

时间复杂度：O(n²)

空间复杂度：O(1)

是否稳定：不稳定¹

算法：

选择排序算法的运作如下：（从前往后）
第1趟，在待排序记录r[1]~r[n]中选出最小的记录，将它与r[1]交换；
第2趟，在待排序记录r[2]~r[n]中选出最小的记录，将它与r[2]交换；
以此类推，第i趟在待排序记录r[i]~r[n]中选出最小的记录，将它与r[i]交换，使有序序列不断增长直到全部排序完毕。

Java实现如下

package prs.rfh.algorithm.sort;

/**
 * @author Swift
 * @version $Algorithm: SelectionSort, v 0.1 2017/1/9 10:29 Swift Exp $$
 */
public class SelectionSort {

    public static int[] SelectionSort(int [] array){
        if (array==null || array.length == 0)throw new IllegalArgumentException("参数非法");
        for (int i = 0; i < array.length-1; i++) {
            for (int j = i+1; j < array.length; j++) {
                if (array[i]>array[j]){
                    int temp = array[j];
                    array[j] = array[i];
                    array[i] = temp;
                }
            }
        }
        return array;
    }

}

【1】稳定性：

举个例子，序列5 8 5 2 9，我们知道第一遍选择第1个元素5会和2交换，那么原序列中2个5的相对前后顺序就被破坏了，所以选择排序不是一个稳定的排序算法。
@author Swift
@date 2017-1-9