1.原理：每次从待排序的数据元素中选出最小(或者最大)的一个元素，存放在已排好序列的起始位置(或者末尾位置)，直到全部待排序的数据元素排完。
2.思路：
(1)第一趟排序，在待排序数据arr[1],arr[2]...arr[n]选出最小的数据，将其与arr[1]进行交换。
(2)第二趟排序：在待排序的arr[2],arr[3].....arr[n]中选出最小的元素与arr[2]进行交换；
。。。。。。。
(3)如此继续。第i趟在待排序数据arr[i],arr[i+1]....arr[n]中选出最小的元素与其进行交换，直至全部完成、
3.举例：
(1)要排序数组:[10,1,35,61,89,36,55]
(2)第一趟排序：[10,1,35,61,89,36,55]
最小数据是1，将1放在首位，也即1和10位置进行交换
排序结果为：[1,10,35,61,89,36,55]
(3)第二趟排序：
对[10,35,61,89,36,55]进行比较，10最小，不用交换
排序结果为：[1,10,35,61,89,36,55]
(4)第三趟排序
对[35,61,89,36,55]进行比较，35最小，不用交换
排序结果为： [1,10,35,61,89,36,55]
(5)第四趟排序
对[61,89,36,55]进行比较，36最小，36和61交换
排序结果为：[1,10,35,36,89,61,55]
(6)第五趟排序
对[89,61,55]进行比较，55最小，55和89交换
排序结果为：[1,10,35,36,55,61,89]
(7)第六躺排序
对[61,89]进行比较，61最小，不需要交换
排序结果为：[1,10,35,36,55,61,89]
4.java实现代码：
import java.util.Scanner; public class SelectSort { public static void main(String[] args) { Scanner sc = new Scanner(System.in); System.out.println("请输入一个数组的大小："); int a = sc.nextInt(); System.out.println("请输入一个数组："); int[] arr = new int[a]; for (int i=0 ; i<a;i++){ arr[i]= sc.nextInt(); } selectSort(arr); } public static void selectSort(int[] arr){ //一定要记住判断边界条件，很多人不注意这些细节，面试官看到你的代码的时候都懒得往下看，你的代码哪个项目敢往里面加？ if(arr==null||arr.length<2){ return; } int temp=0 ; //最小元素的位置只需要在前面的length-2个位置上就可以 for(int i = 0 ; i<arr.length-1;i++){ int min = i ; for (int j=i+1;j<arr.length;j++){ if(arr[min]>arr[j]){ min=j; //记住最小值的位置 } } //交换 temp = arr[i]; arr[i]=arr[min]; arr[min]=temp; } //遍历数组 for(int k = 0 ;k<arr.length;k++){ System.out.print(" "+arr[k]); } } }
import java.util.Arrays;
public class SelectSort {
public static void selectSort(int[] arr){
//一定要记住判断边界条件，很多人不注意这些细节，面试官看到你的代码的时候都懒得往下看，你的代码哪个项目敢往里面加？
if(arr==null||arr.length<2){
return;
}
int temp=0 ;
//最小元素的位置只需要在前面的length-2个位置上就可以
for(int i = 0 ; i<arr.length-1;i++){
int min = i ;
for (int j=i+1;j<arr.length;j++){
if(arr[min]>arr[j]){
min=j; //记住最小值的位置
}
}
//交换
temp = arr[i];
arr[i]=arr[min];
arr[min]=temp;
}
}
public static void main(String[] args) {
int testTime=500000;
int size = 10;
int value=100;
boolean succeed = true;
for(int i = 0 ;i<testTime;i++){
int[] arr1 = generateRandomArray(size,value);
int[] arr2 = copyArray(arr1);
int[] arr3= copyArray(arr1);
selectSort(arr1);
rightMethod(arr2);
if(!isEqual(arr1,arr2)){
succeed=false;
printArray(arr3);
break;
}
}
System.out.println(succeed ? "Nice!" : "Fucking fucked!");
int[] arr = generateRandomArray(size, value);
printArray(arr);
selectSort(arr);
printArray(arr);
}
//产生一个随机数组，数组的长度和值都是随机的，
public static int[] generateRandomArray(int size,int value){
//在java中，Math.random() ->double(0,1)
//(int)((size+1)*Math.random())--->产生的是[0,size]之间的整数
//生成长度随机的数组，数组的最大长度是size的长度
int[] arr = new int[(int)((size+1)*Math.random())];
for(int i = 0 ;i<arr.length;i++){
//针对数组中的每个值都可以随机一下，一个随机数减去另外一个随机数，可能产生正数，也可能产生负数
arr[i]=(int)((value+1)*Math.random())-(int)(value*Math.random());//值也可以是随机的
}
return arr;
}
//复制数组
public static int[] copyArray(int[] arr){
if(arr==null){
return null;
}
int[] res = new int[arr.length];
for(int i = 0 ;i<arr.length;i++){
res[i]=arr[i] ;
}
return res;
}
//绝对正确的方法,这个方法可以时间复杂度很差，但是要保证其准确性
public static void rightMethod(int[] arr){
Arrays.sort(arr);
}
//
public static boolean isEqual(int[] arr1,int[] arr2){
if(arr1==null&&arr2!=null||arr1!=null&&arr2==null){
return false;
}
if (arr1==null&&arr2==null){
return true;
}
if (arr1.length!=arr2.length){
return false;
}
for(int i = 0;i<arr1.length;i++){
if(arr1[i]!=arr2[i]){
return false;
}
}
return true;
}
//打印出数组
public static void printArray(int[] arr){
if(arr==null){
return;
}
for(int i = 0 ;i<arr.length;i++){
System.out.print(arr[i]+" ");
}
System.out.println();
}
}
算法时间复杂度同样还是O(N^2)，记住选择排序的时间复杂度与数据状况无关。