数据结构与算法之选择排序

选择排序（Selection Sort）

核心思想：数据分为已排序区间和未排序区间。
选择排序每次会从未排序区间中找到最小的元素，将其放到已排序区间的末尾。

代码：

public static void sort(int[] arrs) {
        System.out.println("排序前的数组:");
        Arrays.stream(arrs).forEach(x->System.out.print(x + " "));
        //控制总的循环次数，循环n-1次是因为n个数取n-1次之后，剩下最后一个数就不需要比较了
        for(int i=0; i< arrs.length-1; i++) {
            int min = i;
            //每次循环找出剩余未排序的数据中最小的一个数
            for(int j=i; j< arrs.length; j++) {
                if(arrs[min] > arrs[j]) {
                    min = j;
                }
            }
            //将最小的数放到已排序区间的最后
            int temp = arrs[min];
            arrs[min] = arrs[i];
            arrs[i] = temp;
        }
        System.out.println();
        System.out.println("排序后的数组:");
        Arrays.stream(arrs).forEach(x->System.out.print(x + " "));
    }

输出：

排序前的数组:
6 2 7 1 2 10 3 
第1次排序:
1 2 7 6 2 10 3 
第2次排序:
1 2 7 6 2 10 3 
第3次排序:
1 2 2 6 7 10 3 
第4次排序:
1 2 2 3 7 10 6 
第5次排序:
1 2 2 3 6 10 7 
第6次排序:
1 2 2 3 6 7 10 
排序后的数组:
1 2 2 3 6 7 10 

从输出结果分析，第一次排序后的结果：1 2 7 6 2 10 3

从全部数组中，找出了最小的1，并把1和数组第一位置的6，做了互换；

第二次排序找到了最小的2，因为2本来就在第二的位置，所以数组整体顺序没变；

第三次排序找到了最小的另一个2，把2和第三个位置7租了互换；

依次排序…

关键逻辑分析

选择排序还是内外两层循环。

外层循环：

for(int i=0; i< arrs.length-1; i++)

控制总的循环次数，循环n-1次是因为n个数取n-1次之后，剩下最后一个数就不需要比较了。

内层循环：

int min = i;

for(int j=i; j< arrs.length; j++)

每次循环找出剩余未排序的数据中最小的一个数。