選擇排序
這是一個(gè)比較直觀的贮乳，最簡(jiǎn)單的排序算法臣疑，大致是這樣的：首先找到數(shù)組中最小的那個(gè)元素季春，然后谒所，將它和數(shù)組的第一個(gè)元素交換位置（如果第一個(gè)元素已經(jīng)是最小的热康，那么它就和自己交換）。接著百炬，在剩下的元素中找到最小元素褐隆，將它與數(shù)組的第二個(gè)元素交換位置。如此往復(fù)剖踊，直到將整個(gè)數(shù)組排序庶弃。這就是選擇排序。
簡(jiǎn)單實(shí)現(xiàn)如下：
public static void main(String[] args) {
int[] arr = {5, 1, 7, 3, 0, 8, 2, 6, 4, 9};
int N = arr.length;
for(int i=0; i<N; i++) {
int min = i;
for(int j=i+1; j<N; j++) {
if(arr[min] > arr[j]) {
min = j;
}
}
int tmp = arr[i];
arr[i] = arr[min];
arr[min] = tmp;
}
for(int n=0; n<N; n++) {
System.out.println(arr[n] + " ");
}
}
選擇排序很容易誤寫成另外的樣子：
public static void main(String[] args) {
int[] arr = {5, 1, 7, 3, 0, 8, 2, 6, 4, 9};
int N = arr.length;
for(int i=0; i<N; i++) {
for(int j=i+1; j<N; j++) {
if(arr[i] > arr[j]) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
}
}
for(int n=0; n<N; n++) {
System.out.println(arr[n] + " ");
}
}
真正的選擇排序德澈，每次找出一個(gè)最小值歇攻，然后交換位置，最終完成排序梆造，需要交換N次缴守。而上面的代碼，每次比較如果數(shù)組前面的大于后面的就交換位置镇辉，實(shí)際上交換次數(shù)變?yōu)榱耍?N-1) + (N-2) +...+1）次屡穗，復(fù)雜度大大增加了。
