【排序算法】选择排序
1.基本介绍
选择排序基本思想：它首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
2.数据演示
第0次排序：8 5 2 7 3 4 第1次排序：2 5 8 7 3 4 第2次排序：2 3 8 7 5 4 第3次排序：2 3 4 7 5 8 第4次排序：2 3 4 5 7 8 第5次排序：2 3 4 5 7 8
例如在第一次排序中：第一个数8，与后面最小的数交换位置，从而确定最小值，在第2次排序中，已经确定了第一个值2位置不变，所以从5开始，设5为最小值，与后面数进行比较，所以3就和5交换位置，所以3的位置确定，下一次就从8开始，一次类推。
3.算法思路
小编认为要用循环嵌套，内循环执行比较，得出最小值，在外循环中，实现交换元素，以及确定内循环执行的次数。当然还要注意索引的问题，在第一次循环比较时，是第一个元素，第二次循环时，是地二个数字进行比较。
4.代码演示
代码如下：
public class Selet {
public static void main(String[] args) {
int arr[]={8,5,2,7,3,4};
int j;
for ( j=0; j < arr.length-1; j++) {
int min=arr[j];
int minindex=j;
for (int i = j+1; i < arr.length ; i++) {
if(min>arr[i]){
//说明最小值不是假设的数
min=arr[i];//重置最小值
minindex=i;//重置最小值的下标
}
}
//所以交换两个数组中的元素
arr[minindex]=arr[j];
arr[j]=min;
System.out.println("第"+(j+1)+"次排序后的队列为"+Arrays.toString(arr));
}
System.out.println("所以最终排序后的数列为"+ Arrays.toString(arr));
}
}小编这里实现比较的元素时，设定arr[0]是第一次对比的对象，在每次循环时，对比的对象索引都要加一，所以为arr[ j ],设定它为最小值，来与后面的比较。在交换元素时，将数值小的元素存在一个min变量里，索引也是，在交换元素时，数值大的索引不变，值等于最小值；数值晓得索引不变，值等于最大值。
演示结果：
第1次排序后的队列为[2, 5, 8, 7, 3, 4] 第2次排序后的队列为[2, 3, 8, 7, 5, 4] 第3次排序后的队列为[2, 3, 4, 7, 5, 8] 第4次排序后的队列为[2, 3, 4, 5, 7, 8] 第5次排序后的队列为[2, 3, 4, 5, 7, 8] 所以最终排序后的数列为[2, 3, 4, 5, 7, 8]
5.代码优化
在上述输出结果中第4次和第5次重合了，小编这里用了一个条件语句实现
public class Selet {
public static void main(String[] args) {
int arr[]={1,5,2,7,3,4};
int i;
int j;
int index=0;
for ( j=0; j < arr.length-1; j++) {
int min=arr[j];
int minindex=j;
for ( i = j+1; i < arr.length ; i++) {
if(min>arr[i]){
//说明最小值不是假设的数
min=arr[i];//重置最小值
minindex=i;//重置最小值的下标
}
}
//所以交换两个数组中的元素
if(minindex!=j){
index++;
arr[minindex]=arr[j];
arr[j]=min;
System.out.println("第"+index+"次排序后的队列为"+Arrays.toString(arr));
}
}
System.out.println("所以最终排序后的数列为"+ Arrays.toString(arr));
}
}小编这里当交换位置时minindex才不等于原来的值，所以才输出排序次数以及排序结果，index只是为了记录排序的次数
演示结果：
第1次排序后的队列为[2, 5, 8, 7, 3, 4] 第2次排序后的队列为[2, 3, 8, 7, 5, 4] 第3次排序后的队列为[2, 3, 4, 7, 5, 8] 第4次排序后的队列为[2, 3, 4, 5, 7, 8] 所以最终排序后的数列为[2, 3, 4, 5, 7, 8]
6.时间演示
小编在循环前后测试了排序循环的时间
这是在排序之前（for循环之前）
这是在排序之后（即for循环过后）
如图所示，在100000个随机数据中只用了3秒，比小编上期的冒泡排序少了很多（冒泡排序http://t.csdnimg.cn/9mqj4）
7.总结
选择排序的时间复杂度为On(n^2) ，空间复杂度为O(1) 。尽管它在实际应用中不是很高效，但由于其简单易懂的特性，常用于教学和对小型数据集的排序。
限于小编能力有限，本篇难免有些瑕疵，欢迎各位uu给出宝贵意见。
要是觉得本篇对你有帮助，请给小编一个小小的赞吧。
腾讯云开发者
