选择排序

 1/**
 2 * 选择排序的Java实现<br>
 3 * 若有数组A[N]
 4 * <p>
 5 * 选择排序和插入排序有些类似，从第p个元素开始，
 6 * 每次从剩余的N-p元素中选出最小的那个元素，放在p个元素的末尾。<br>
 7 * 选择排序同样保证了前p个元素是已经排序的。
 8 * <p>
 9 * 若有数组【4，19，12，3，25，16】，选择排序的过程为：
10 * 
11 * <pre>
12 *      原数组     4 19 12 3 25 16
13 *      第一次     3 19 12 4 25 16
14 *      第二次     3 4 12 19 25 16
15 *      第三次     3 4 12 19 25 16
16 *      第四次     3 4 12 16 25 19
17 *      第五次     3 4 12 16 19 25
18 *      第六次     3 4 12 16 19 25
19 * </pre>
20 * <p>
21 * <p>
22 * 选择排序的时间复杂度和冒泡排序一样，为O(N^2);<br>
23 * 选择排序是不稳定排序，如序列【5，4，5，3，6】第一次选择后变为【3，4，5，5，6】，
24 * 其中两个「5」的相对位置发生了变化。
25 *
26 * @author wangy
27 * @version 1.0
28 * @date 2021/7/5 / 14:28
29 */
30public class SelectSort {
31
32    static void sort(int[] a) {
33        for (int i = 0; i < a.length; i++) {
34            int tmp = a[i];
35            int index = i;
36            // 查找最小值
37            for (int j = i + 1; j < a.length; j++) {
38                if (a[j] < a[index]) {
39                    index = j;
40                }
41            }
42            // 交换位置
43            a[i] = a[index];
44            a[index] = tmp;
45            System.out.println("===>" + Arrays.toString(a));
46        }
47    }
48
49    public static void main(String[] args) {
50        int[] a = new int[] { 4, 19, 12, 3, 25, 16 };
51        SelectSort.sort(a);
52        System.out.println(Arrays.toString(a));
53    }
54
55}