文章目录
前言
动图演示
特点
基本思想
算法描述
总结
代码实现
前言
选择排序是一种简单直观的排序方法，每次寻找排序中最小值，然后放到排序序列的末尾。
动图演示
特点
时间复杂度
最好情况：O(n2)
平均情况：O(n2)
最坏情况：O(n2)
空间复杂度：O(1)
稳定性：不稳定
基本思想
在未排序序列中找到最小元素，存放到排序序列的起始位置
再从剩余未排序元素中继续寻找最小元素，然后放到排序序列末尾
以此类推，直到所有元素均排序完毕
算法描述
n个记录的直接选择排序可经过n-1趟直接选择排序得到有序结果。具体算法描述如下：
初始状态：无序区为R[1…n]，有序区为空；
第i趟排序(i=1,2,3…n-1)开始时，当前有序区和无序区分别为R[1…i-1]和R(i…n）。该趟排序从当前无序区中-选出关键字最小的记录 R[k]，将它与无序区的第1个记录R交换，使R[1…i]和R[i+1…n)分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区；
n-1趟结束，数组有序化了。
总结
选择排序就是从第一趟开始，用第一个元素和剩下中的每一个元素比较，如果比第一个小，就和第一个元素交换值，最后使得第一个元素中的值最小，第二趟选择出第二小的放到第二元素，依次，使得数组有序。
代码实现
package demo4; import java.util.Arrays; /** * 简单选择排序 * * 2019年8月19日 */ public class SelectSort { public static void main(String[] args) { int[] arr = new int []{5,3,4,9,7,6,1,2}; System.out.println("排序前："+Arrays.toString(arr)); selectSort(arr); System.out.println("排序后："+Arrays.toString(arr)); } //简单选择排序 public static void selectSort(int[] arr){ //定义一个临时变量存储最小值 int temp = 0; int num=0; for(int i=0;i<arr.length;i++){ //临时变量存放最小值 temp= arr[i]; num=i; for(int j=i;j<arr.length;j++){ if(temp>arr[j]){ temp=arr[j]; num =j; } } //第几轮就和第几个交换 int x; x=arr[i]; arr[i] = temp; arr[num]=x; } } } /** * 选择排序 */ public class Demo2 { public static void main(String[] args) { int[] a=new int[10]; //用随机数给数组元素赋值 for(int i=0;i<a.length;i++){ a[i]=(int)(Math.random()*100); } //数组遍历标准方法 System.out.print("["); for(int i=0;i<a.length;i++){ if(i==a.length-1){ System.out.print(a[i]); }else{ System.out.print(a[i]+", "); } } System.out.println("]"); //做交换中间值用 int tmp=0; for(int i=0;i<a.length-1;i++){//length-1是因为最后一个元素不需要进行比较 //遍历所有元素，和后面所有元素进行比较，保证正序输出 for(int j=i+1;j<a.length;j++){//i+1保证是i后面的元素 if(a[i]>a[j]){ tmp=a[i]; a[i]=a[j]; a[j]=tmp; } } } System.out.println(Arrays.toString(a)); } }
