选择排序

1. 算法思想
  在一个长度为N的无序数组中，第1趟遍历N个元素，找出最小的元素与第一个元素交换;第 2 趟遍历剩下的N − 1个数据，找出其中最小的元素与第二个元素交换; ... ;第N − 1趟遍历剩下两个元素，找出其中最小的与第N − 1个元素交换，至此排序完成。

2. 算法实现

import java.util.Arrays;

/**
 * @Author: 落脚丶
 * @Date: 2017/12/05
 * @Time: 下午5:23
 * @ClassName: SelectionSort
 * @Description: 选择排序
 */
public class SelectionSort {
    public static void main(String[] args) {
        int[] test = new int[]{2,83,12,54,23,67,1,56};
        selectionSort(test);
        System.out.println(Arrays.toString(test));
    }
    public static void selectionSort(int[] a) {
        for(int i = 0; i < a.length - 1; i++) {
            int index = i; // 最小元素的坐标，假设开头的元素最小。
            for (int j = i + 1; j < a.length; j++) {
                if (a[j] < a[j - 1]) {
                    index = j;
                }
            }
            if (index != i) {
                swap(a, i, index);
            }
        }
    }
    /**
    * @Date: 2017/12/05
    * @Time: 下午5:25
    * @Method: swap
    * @Description: 交换数组两个元素的位置
    */
    public static void swap(int[] a, int b, int c) {
        int tem = a[c];
        a[c] = a[b];
        a[b] = tem;
    }
}

3. 算法复杂度

平均时间复杂度为： O(n²);
不稳定，比如序列[5，5，3]第一趟就将第一个[5]与[3]交换，导致第一个5挪动到第二个5后面。