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)
選擇排序的原理大致是，首先找到數(shù)組中最小的那個(gè)元素挽霉，其次，將它和數(shù)組的第一個(gè)元素交換位置（如果第一個(gè)元素就是最小元素那么它就和自己交換）变汪。再次侠坎，在剩下的元素中找到最小的元素，將它與數(shù)組的第二個(gè)元素交換位置疫衩。如此往復(fù)硅蹦，直到將整個(gè)數(shù)組排序荣德。
選擇排序有兩個(gè)鮮明的特點(diǎn)：
- 運(yùn)行時(shí)間和輸入無關(guān)闷煤。
- 數(shù)據(jù)移動是最少的。
