选择排序和冒泡排序有点类似，都是经过比较排序后把较小元素排在前面，区别在于冒泡排序每次仅和相邻的元素进行比较，且比较完后就进行元素位置交换；选择排序是每个元素和其之后位置的元素进行比较，每次比较取最小的元素下标，最后再把最小元素排在最前面。举个例子：8 4 2 7 这个数组，下标为0的元素即8与4进行交换，4比8小，记录当前最小下标1，再下标为1的元素4与2进行比较，2较小，记录2的下标2,2再与元素7比较，得到最小数下标2，元素2与8进行交换，得到新数组排列为2 4 8 7，此时最小数下标+1，即4与其后元素比较，得到新数组排序2 4 8 7， 再元素8与其后元素比较，得到最终数组2 4 7 8。选择排序比冒泡排序相比，大大减少了交换次数，时间复杂度为O(n^2)。
此处用java实现一个有逼格的选择排序算法。
import java.util.Comparator;
public interface Sorter {
/**
* 通过自身实现 Comparable接口进行比较排序
* @see Comparable
* @param list
*/
<T extends Comparable<T>> void sort(T[] list);
/**
* 通过补救性排序器Comparator 进行排序
* @see Comparator
* @param list
* @param cmpt
*/
<T> void sort(T[] list, Comparator<T> cmpt);
}
import java.util.Comparator;
public class SelectSorter implements Sorter {
@Override
public <T extends Comparable<T>> void sort(T[] list) {
for(int i = 0; i < list.length - 1; i++) {
int minIndex = i;
for(int j = i + 1; j < list.length; j++) {
if(list[j].compareTo(list[minIndex]) < 0) {
minIndex = j;
}
}
if(minIndex != i) {
swap(list, i, minIndex);
}
}
}
@Override
public <T> void sort(T[] list, Comparator<T> cmpt) {
for(int i = 0; i < list.length - 1; i++) {
int minIndex = i;
for(int j = i + 1; j < list.length; j++) {
if(cmpt.compare(list[j], list[minIndex]) < 0) {
minIndex = j;
}
}
if(minIndex != i) {
swap(list, i, minIndex);
}
}
}
public <T> void swap(T[] list, int i, int j) {
T temp = list[i];
list[i] = list[j];
list[j] = temp;
}
}
注：此处为整理算法，部分代码设计参考网上
参考链接