1.什么是选择排序
? ? 我有一个无序数组A,第一次我先把A最小的数字拿出来,放在数组B的第一位,然后第二次,我从数组A剩下元素中获取到最小的数字,放到数组B的第二位,如此类推,每一轮我们都从数组A中获取到剩余元素的最小一个,放到数组B,最后数组B为有序的数组.
? ? 假设我有一个数组,6,4,3,1,2,5.我想进行排序,所以我需要遍历这个数组.假设第一轮遍历,我挨个去比较,我获取到最小的数字是1即minIndex=3,我的数字1需要排在第一个数字的位置,即索引0,就用0索引和3索引位置的元素交换,变为1,4,3,6,2,5;第二轮最小的元素肯定是2,即minIndex=4,所以我们1和4索引元素换一下位置,变为1,2,3,6,4,5如此类推,每次循环找到最小的值,minIndex作为标记,最后再和当前遍历到的位置i进行交换.
2.代码实现
? ? 每一轮遍历我都可以通过比较拿到最小的一个值,用minIndex标记他为最小值,用I和minIndex位置进行交换.这样我们就可以认为,经过I轮循环之后arr[0...i) 是有序的；arr[i...n) 是无序的.
?
// ? 从前向后扫描,对于每一个 i,寻找 arr[0...i] 区间中的最小值,
//记这个最小值的索引是 minIndex，然后，
//只需要每次将 arr[i] 和 arr[minIndex] 交换位置即可.
public static <E extends Comparable<E>> void sort(E[] arr){
// arr[0...i) 是有序的；arr[i...n) 是无序的
for(int i = 0; i < arr.length; i ++){
// 选择 arr[i...n) 中的最小值
int minIndex = i;
for(int j = i; j < arr.length; j ++){
if(arr[j].compareTo(arr[minIndex]) < 0)
minIndex = j;
}
swap(arr, i, minIndex);
}
}
private static <E> void swap(E[] arr, int i, int j){
E t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}3.选择排序的时间复杂度?
? ? 第一轮循环我们需要执行,j次,第二轮循环执行j-1次,如此类推最后一次,只执行一次,所以总共执行了1+2+3...+j.所以省略掉常数项以及低次幂忽略,算法复杂度为j^2.即n^2.
?
