在网上搜索算法的博客，发现一个比较悲剧的现象非常普遍：
- 原理讲不清，混乱
- 啰嗦
- 图和文对不上
- 不可用，甚至代码还出错
我总结一个清晰不罗嗦版：
原理：
- 从数组头元素索引i开始，寻找后面最小的值（比i位置值小），进行交换；
- 索引i依次+1
选择排序时间复杂度
选择排序的时间复杂度是O(N2)。
假设被排序的数列中有N个数。遍历一趟的时间复杂度是O(N)，需要遍历多少次呢？N-1！因此，选择排序的时间复杂度是O(N2)。
选择排序稳定性
选择排序是稳定的算法，它满足稳定算法的定义。
算法稳定性 -- 假设在数列中存在a[i]=a[j]，若在排序之前，a[i]在a[j]前面；并且排序之后，a[i]仍然在a[j]前面。
JAVA代码
package Sort;
public class Selection {
public static void main(String[] args) {
int arr[] = {1, 12, 5, 26, 7, 14, 3, 7, 2};
Selection ob = new Selection();
ob.selectionSort(arr);
System.out.println("选择排序结果：");
printArray(arr);
}
public void selectionSort(int[] arr) {
int i, j, minIndex, tmp;
int n = arr.length;
for (i = 0; i < n - 1; i++) {
minIndex = i; //最小值的索引位置
for (j = i + 1; j < n; j++)
if (arr[j] < arr[minIndex])
minIndex = j;
if (minIndex != i) {
tmp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = tmp;
}
}
}
public static void printArray(int arr[])
{
int n = arr.length;
for (int i=0; i<n; ++i)
System.out.print(arr[i]+" ");
System.out.println();
}
}