選擇排序（Selection sort）是一種簡單直觀的排序算法屑那。
它的工作原理如下哈踱。首先在未排序序列中找到最小（大）元素慢显，存放到排序序列的起始位置爪模，然后，再從剩余未排序元素中繼續(xù)尋找最屑栽濉（大）元素屋灌，然后放到已排序序列的末尾。以此類推应狱，直到所有元素均排序完畢共郭。
選擇排序的主要優(yōu)點(diǎn)與數(shù)據(jù)移動有關(guān)。如果某個元素位于正確的最終位置上疾呻，則它不會被移動除嘹。選擇排序每次交換一對元素，它們當(dāng)中至少有一個將被移到其最終位置上罐韩，因此對 n 個元素的表進(jìn)行排序總共進(jìn)行至多 n-1 次交換憾赁。在所有的完全依靠交換去移動元素的排序方法中，選擇排序?qū)儆诜浅：玫囊环N散吵。
/**
* 選擇排序的思想其實和冒泡排序有點(diǎn)類似龙考，都是在一次排序后把最小的元素放到最前面。
* 但是過程不同矾睦，冒泡排序是通過相鄰的比較和交換晦款。而選擇排序是通過對整體的選擇。
* 舉個栗子枚冗，對 5,3,8,6,4 這個無序序列進(jìn)行簡單選擇排序缓溅，
* 首先要選擇 5 以外的最小數(shù)來和 5 交換，也就是選擇 3 和 5 交換赁温，一次排序后就變成了 3,5,8,6,4.
* 對剩下的序列一次進(jìn)行選擇和交換坛怪，最終就會得到一個有序序列淤齐。
* 其實選擇排序可以看成冒泡排序的優(yōu)化，因為其目的相同袜匿，只是選擇排序只有在確定了最小數(shù)的前提下才進(jìn)行交換更啄，大大減少了交換的次數(shù)。
* 選擇排序的時間復(fù)雜度為 O(n^2)
*
* @author wb
*/
public class SelectSort {
public static void selectSort(int[] arr) {
if (arr == null || arr.length == 0)
return;
int minIndex;
for (int i = 0; i < arr.length - 1; i++) { //只需要比較n-1次
minIndex = i;
//從i+1開始比較居灯，因為minIndex默認(rèn)為i了祭务，i就沒必要比了。
for (int j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
if (minIndex != i) { //如果minIndex不為i怪嫌，說明找到了更小的值义锥，交換之。
swap(arr, i, minIndex);
}
}
}
public static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
白話分析：
- 從第一個元素循環(huán)遍歷每一個元素岩灭，找到最小的元素拌倍，遍歷一輪結(jié)束后和第一個元素進(jìn)行交換，此時最小值處于數(shù)組前面川背；
- 重復(fù)步驟一贰拿，遍歷剩余的序列；
- 每一輪完畢后剩余隊列最小者都會被交換到最左側(cè)熄云；
- 最終得到一個有序隊列；
選擇排序.gif
