简单选择排序
前言：在博客写这些文章的目的用于记录所学，怕以后忘了，如果哪里写的不对欢迎指正，谢谢！！
学习目标：掌握简单选择排序原理和思想
一、前提知识
排序算法概念、时间复杂度。可前往此网址 排序算法学习01_算法基础介绍阅读
二、简单选择排序介绍
简单选择排序是属于选择排序算法的其中一种简单排序。该算法每进行一次重复走访时，只选择一个值进行排序，简单选择排序的名字也由此而来
三、简单选择排序工作原理
刚开始所有元素都处于未排序序列，然后每次通过保存未排序序列的第一个元素且先指定为最大/最小元素，然后再从剩余序列中找元素与之比较，把找到的最大/小元素与未排序序列的第一个元素交换位置。那么原本未排序序列的第一个位置的元素，即成为一个有序序列中的值。继续下一次走访
四、简单选择排序设计思路
1.既然需要重复走访
- 那就要控制两个循环，最里层的循环用来找剩余序列中最大/小元素，最外层则用来决定重复走访几次。每完成一次走访则有一个元素已排序好
2.每次都是用未排序序列的第一个元素，与剩余序列的元素进行比较，得到的元素放在已排序序列的末尾
- 那么获取剩余序列中的元素，肯定不能保存它的值，需要记录最大/小值的下标，否则你想，我们最终是要实现数组中某两个元素进行交换，如果保存值的话，怎么知道该值在哪个索引下
- 只需要拿到最大/小元素的==索引==，根据索引把值放置在未排序序列的第一个位置即可
3.得到最大/小元素的所在位置，那么如何放在已排序序列的末尾呢
- 需要一个辅助变量，让未排序序列第一个元素与走访时得到最大/小元素进行交换
五、根据以上思路写一个选择排序实例
要求对以下这个数列进行递增排序：{3，2，5，1，7，9，8}
package com.migu.sortingAlgorithm;
import java.util.Arrays;
/**
* 简单选择排序
*/
public class SimpleSelectionSort {
public static void main(String[] args) {
int a[] = {3,2,5,1,7,9,8};
// 最外层的循环，为何用a.length-1，为何不对所有元素进行访问呢？假定有8个元素，其他7个在重复走访时已确定，那另一个必然也是排序的
for(int i = 0;i < a.length-1;i++){
int min = i; // 每次重复走访保存未排序序列的第一个值的索引
for(int j = i+1;j < a.length;j++){ // 从剩余序列开始判断
if(a[j] < a[min]) min = j; // 保存未排序序列的最小值中的索引
}
// 如果索引未发生改变，则表明未排序序列的第一个值是合法的
// 否则使用未排序序列的第一个值和后面的值进行交换
if(min != i){
int temp = a[min]; // 建立临时变量来辅助操作，保存谁都可以，达成交换目的即可
a[min] = a[i];
a[i] = temp;
}
}
System.out.println(Arrays.toString(a)); // 调用工具类输出数组
}
}
在这里插入图片描述
六、时间复杂度分析
讨论一个算法的时间复杂度，一般都是看最坏的情况： 简单选择排序算法的时间复杂度为O(n^2).更多特殊情况请参考其他书籍或博客
七、总结
简单选择排序，每完成一次重复走访时，比较所有元素，只有一个元素会完成排序，且该元素位置是已确定。简单选择排序从队头开始排序下来
与我们前面所讲的冒泡排序相比，冒泡排序算法每次排序时都要大量比较，且会在数组上移动大量数据，而选择排序算法则是通过大量比较显然是比冒泡好的。
