排序算法之选择排序
基本思想
选择排序算法的基本思想是：首先，找到数组中最小的那个元素，其次，将它和数组的第一个元素交换位置（如果第一个元素就是最小元素那么它就和自己交换）。再次，在剩下的元素中找到最小的元素，将它和数组的第二个元素交换位置。如此重复，直到将整个数组排序。
代码实现
package sortdemo;
public class SelectSort {
public static void main(String[] args){
int[] arr = {3,0,6,5,7,4,9,8,1};
System.out.println("排序之前：");
for(int i=0;i<arr.length;i++){
System.out.print(arr[i]+" ");
}
selectSort(arr);
System.out.println();
System.out.println("排序之后:");
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
}
public static void selectSort(int[] arr){
for(int i=0;i<arr.length;i++){
int min = i;
for(int j=i+1;j<arr.length;j++)
if(arr[j]<arr[min]) min=j;//交换arr[i]和arr[min]
swap(arr,min,i);
}
}
public static void swap(int[] arr,int a,int b){
int temp = arr[a];
arr[a]=arr[b];
arr[b]=temp;
}
}
复杂度
选择排序的时间复杂度：简单选择排序的比较次数与序列的初始排序无关。假设待排序的序列有N个元素，则比较次数永远都是N(N-1)/2。而移动次数与序列的初始排序有关。当序列正序时，移动次数最少，为0。当序列反序时，移动次数最多，为3N(N-1)/2。综上，简单选择排序的时间复杂度为O(N^2)。
