public class Selection {
public static void sort(Comparable[] a) {
int N = a.length;
for (int i = 0; i < N; i++) {
int min = i;
for (int j = i + 1; j < N; j++) {
if (less(a[j], a[min])) {
min = j;
}
}
exch(a, i, min);
}
}
public static boolean less(Comparable v, Comparable w) {
return v.compareTo(w) < 0;
}
public static void exch(Comparable[] a, int i, int j) {
Comparable t = a[i];
a[i] = a[j];
a[j] = t;
}
public static void show(Comparable[] a) {
for (int i = 0; i < a.length; i++) {
System.out.print(a[i]);
}
System.out.println();
}
public static boolean isSorted(Comparable[] a) {
for (int i = 1; i < a.length; i++) {
if (less(a[i], a[i - 1])) {
return false;
}
}
return true;
}
public static void main(String[] args) {
String[] a = {"e", "a", "b", "f"};
sort(a);
assert isSorted(a);
show(a);
}
}
class Selection:
def sort(self, data):
for i in range(0, len(data) - 1):
min_index = i
for j in range(i + 1, len(data)):
if self.less(data[min_index], data[j]):
min_index = j
self.exch(data, i, min_index)
def less(self, x, y):
return x > y
def exch(self, data, i, min_index):
data[i], data[min_index] = data[min_index], data[i]
if __name__ == "__main__":
selection = Selection()
s = [3, 4, 1, 6, 2, 9, 7, 0, 8, 5]
selection.sort(s)
print(s)
选择排序的原理大致是，首先找到数组中最小的那个元素，其次，将它和数组的第一个元素交换位置（如果第一个元素就是最小元素那么它就和自己交换）。再次，在剩下的元素中找到最小的元素，将它与数组的第二个元素交换位置。如此往复，直到将整个数组排序。
选择排序有两个鲜明的特点：
- 运行时间和输入无关。
- 数据移动是最少的。
