初识选择排序：
算法思想[以升序为例]：
第一趟选择排序时，从第一个记录开始，通过n-1次关键字的比较，从第n个记录中选出关键字最小的记录，并和第一个记录进行交换
第二趟选择排序时，从第二个记录开始，通过n-2次关键字的比较，从第n-1个记录中选出关键字最小的记录，并和第二个记录进行交换
…
第i趟选择排序时，从第i个记录开始，通过n-i次关键字的比较，从n-i+1个记录中选择出关键字最小的记录，并和第i个记录进行交换
反复进行上述步骤，经过n-1趟选择排序，将把n-1个记录排到位，最后剩下的那个元素同样已经就位，所以共需进行n-1趟选择排序
文字描述[以升序为例]：
将数组分为两个子集，排序的和未排序的，每一轮从未排序的子集中选出最小的元素，放入排序子集，重复上述步骤，直至整个数组有序
算法实现：
代码如下：
package bin_find; import java.util.Arrays; public class selectionSort { public static void main(String[] args) { int[] a={5,3,7,2,1,9,8,4}; selection(a); } private static void selection(int[] a){ for(int i=0;i<a.length-1;i++) {//n个元素参与排序，需要进行n-1次 for (int j = i + 1; j < a.length; j++) {//每轮i+1---a.length个元素之间相比较 if (a[i] > a[j]) {//前者大于后者，则进行交换 swap(a, i, j); } } System.out.println("第"+(i+1)+"轮选择排序的结果"+Arrays.toString(a)); } } public static void swap(int arr[],int i,int j){ int t=arr[i]; arr[i]=arr[j]; arr[j]=t; } }
输出如下：
第1轮选择排序的结果[1, 5, 7, 3, 2, 9, 8, 4] 第2轮选择排序的结果[1, 2, 7, 5, 3, 9, 8, 4] 第3轮选择排序的结果[1, 2, 3, 7, 5, 9, 8, 4] 第4轮选择排序的结果[1, 2, 3, 4, 7, 9, 8, 5] 第5轮选择排序的结果[1, 2, 3, 4, 5, 9, 8, 7] 第6轮选择排序的结果[1, 2, 3, 4, 5, 7, 9, 8] 第7轮选择排序的结果[1, 2, 3, 4, 5, 7, 8, 9]
优化后的算法实现：
优化思路
减少交换次数，每一轮可以先找到最小的索引，再每轮最后再交换元素
代码如下：
package bin_find; import java.util.Arrays; public class selectionSort { public static void main(String[] args) { int[] a={5,3,7,2,1,9,8,4}; selection(a); } private static void selection(int[] a){ //代表每轮选择最小元素要交换到的目标索引 for(int i=0;i<a.length-1;i++) { int s = i;//代表最小元素的索引[这里是升序]---第一次最小元素的索引为1，第二次最小元素的索引为2..... //从当前最小元素的下一位元素开始直到最后一个元素---完成一次选择排序 for (int j = s + 1; j < a.length; j++) { //[这里是升序]，前者大于后者，则将更小数的索引值赋值给s,因为变量s本身代表的含义为最小元素的索引 if (a[s] > a[j]) { s = j; } } if (s != i) {//若不是同一个数，则进行交换 swap(a, s, i); } System.out.println("第"+(i+1)+"轮选择排序的结果"+Arrays.toString(a)); } } public static void swap(int arr[],int i,int j){ int t=arr[i]; arr[i]=arr[j]; arr[j]=t; } }
输出：
第1轮选择排序的结果[1, 3, 7, 2, 5, 9, 8, 4] 第2轮选择排序的结果[1, 2, 7, 3, 5, 9, 8, 4] 第3轮选择排序的结果[1, 2, 3, 7, 5, 9, 8, 4] 第4轮选择排序的结果[1, 2, 3, 4, 5, 9, 8, 7] 第5轮选择排序的结果[1, 2, 3, 4, 5, 9, 8, 7] 第6轮选择排序的结果[1, 2, 3, 4, 5, 7, 8, 9] 第7轮选择排序的结果[1, 2, 3, 4, 5, 7, 8, 9]
未进行优化的算法输出;
进行优化的算法输出：
通过比较二者的输出结果，我们能够很明显的感觉到，经过优化后的算法在实现的过程中，数据之间的交换次数明显减少
选择排序 VS 冒泡排序：
1:二者的平均复杂度都是O(n^2),但是当有序数组使用冒泡排序时，其时间复杂度为O(n)
2:选择排序一般要快于冒泡排序，因为其交换的次数少
3：但如果集合有序度高，那么冒泡排序优先于选择排序
例：在上篇文章的冒泡排序优化算法中，我们通过设置变量，去判断当前的数组元素是否发生交换，如果未发生交换，则证明当前数组已经有序，不再进行排序
4：冒泡排序属于稳定排序算法，而选择属于不稳定排序
稳定 VS 不稳定：即为两个大小相等的数，在参与排序之前具有先后关系，若排序完成，这两个数的先后顺序并未发生改变，那么即为稳定排序，否则为不稳定排序
举例:
(3,3,2)
对于上述数组:
参与冒泡排序：
第一轮：3和3相等，无需交换位置，3和2交换位置
第二轮：3和2交换位置
排序结束，排序后的结果为(2,3,3)
参与选择排序：
第一轮：将3取出，与3比较，3不满足大于3，再与2进行比较，满足大于2，交换位置
第二轮:将3取出,与3进行比较，不满足大于3
排序结束，排序成功，排序后的结果为(2,3,3)
通过两种方法的排序结果，我们不难看出通过冒泡排序算法，两个大小相等的数的先后关系并没有发生改变，即为稳定的排序，而通过选择排序算法，两个大小相等的数的先后关系发生了改变，即为不稳定的排序
