冒泡排序：在每一次比較的時候，如果發現相鄰兩數的次序不對，都會馬上就把兩數進行對調。
選擇排序：則在比較過程中（內循環里面）并不進行對調，而是先記錄下最小（大）數的下標，在一次掃描完成后再進行對調。?
1、算法思想
在要排序的一組數中，選出最小（或者最大）的一個數與第 i（i=0）個位置的數交換；然后在剩下的數當中再找最小（或者最大）的與第i+1個位置的數交換，依次類推，直到第n-1個元素（倒數第二個數）和第n個元素（最后一個數）比較為止。
2、代碼實現
~~~
/**
* 在要排序的一組數中，選出最小（或者最大）的一個數與第 i（i=0）個位置的數交換； 然后在剩下的數當中再找最小（或者最大）的與第i+1個位置的數交換， 依次類推，直到第n-1個元素（倒數第二個數）和第n個元素（最后一個數）比較為止。
*/
private static void SimpleSelectSort(int[] source) {
if (source.length <= 1 || source == null) {// 習慣，參數判斷
return;
}
for (int i = 0; i < source.length - 1; i++) { // i < source.length尚可
int j = i + 1;
int min = source[i]; // 最小值
int minIndex = i; // 最小值下標
while (j < source.length) {
if (source[j] < min) {
min = source[j];
minIndex = j;
}
j++;
}
if (minIndex != i) { // 3次賦值
source[i] = source[minIndex] + (source[minIndex] = source[i]) * 0;
}
printArr(source);
}
}
~~~
3、算法分析
1.時間復雜度
選擇排序的交換操作介于 0 和 (n - 1）次之間。
選擇排序的比較操作為 n (n - 1）/ 2次。
選擇排序的賦值操作介于 0 和 3 (n - 1）次之間(n-1次交換，每次交換需要賦值3次)?t = a, a = b, b = t。
比較次數O(n^2），比較次數與關鍵字的初始狀態無關，總的比較次數N=(n-1）+(n-2）+...+1=n*(n-1）/2。
交換次數O(n），最好情況是，已經有序，交換0次；最壞情況交換n-1次，逆序交換n/2次。
交換次數比[冒泡排序](http://baike.baidu.com/view/254413.htm)少多了，由于交換所需CPU時間比比較所需的CPU時間多，n值較小時，選擇排序比冒泡排序快。
2.穩定性
選擇排序是給每個位置選擇當前元素最小的，比如給第一個位置選擇最小的，在剩余元素里面給第二個元素選擇第二小的，依次類推，直到第n-1個元素，第n個元素不用選擇了，因為只剩下它一個最大的元素了。那么，在一趟選擇，如果一個元素比當前元素小，而該小的元素又出現在一個和當前元素相等的元素后面，那么交換后穩定性就被破壞了。比較拗口，舉個例子，序列5 8 5 2 9，我們知道第一遍選擇第1個元素5會和2交換，那么原序列中兩個5的相對前后順序就被破壞了，所以選擇排序是一個不穩定的排序算法。
4、算法改進
**二元選擇排序**
簡單選擇排序，每趟循環只能確定一個元素排序后的定位。我們可以考慮改進為每趟循環確定兩個元素（當前趟最大和最小記錄）的位置,從而減少排序所需的循環次數。改進后對n個數據進行排序，最多只需進行[n/2]趟循環即可。具體實現如下：（類冒泡）
~~~
/**
* 簡單選擇排序，每趟循環只能確定一個元素排序后的定位。 我們可以考慮改進為每趟循環確定兩個元素（當前趟最大和最小記錄）的位置。 從而減少排序所需的循環次數。改進后對n個數據進行排序，最多只需進行[n/2]趟循環即可。
*/
private static void TwoSelectSort(int[] source) {
int n = source.length;
if (n <= 1 || source == null) {// 習慣，參數判斷
return;
}
int minIndex, maxIndex, tempI;
for (int i = 0; i < n / 2; i++) {
minIndex = maxIndex = i;
for (int j = i + 1; j < n - i; j++) {
if (source[j] < source[minIndex]) {
minIndex = j;
continue;
}
if (source[j] > source[maxIndex]) {
maxIndex = j;
}
}
if (minIndex != i) { // 3次賦值
source[i] = source[minIndex] + (source[minIndex] = source[i]) * 0;
}
if (maxIndex == i) { // 此時最大值已被替換到minIndex處
maxIndex = minIndex;
}
if (maxIndex != n - i - 1) {
source[n - i - 1] = source[maxIndex] + (source[maxIndex] = source[n - i - 1]) * 0;
}
printArr(source);
}
}
~~~
冒泡排序改進算法之每趟循環確定兩個元素時，不用考慮 if（maxIndex==i），因為其每趟比較只要不符合排序就要交換位置，而不是僅僅記錄其索引的改變。
源碼地址：[https://github.com/zxiaofan/Algorithm/blob/master/src/sort/SelectSort.java](https://github.com/zxiaofan/Algorithm/blob/master/src/sort/SelectSort.java)
