以下排序规则按从左向右依次递增排序。即{3, 5, 1, 10, 0, 100, 3, 9} 排序结果为{0, 1, 3, 3, 5, 9, 10, 100}。
排序主要有两类操作：比较 与 交换位置。
冒泡排序每次是比较相邻两个元素之间大小，并判断是否要交换位置，如果位置不对每次都要交换位置。
选择排序与冒泡排序相比，并未减少比较次数，而是在交换位置上进行了优化。
选择排序是每次记录一个位置，然后与所有为排序的元素进行比较，最终得到一个最值。（可以选择每次记录最大值，也可以选择每次记录最小值）
以最小值为例：
1. 从左向右，每次记录一个位置。
2. 这个位置上的值与其他所有未排序的每一个位置的值进行比较。
3. 如果比较的值比记录位置的值小，记录这个比较值的位置。
选择排序第一种写法：每次从左向右找出最小的值
/**
* 比较排序，每次记录最小的值位置
*/
private void selectionSortMin(int[] pArray) {
if (pArray == null) {
throw new NullPointerException();
}
int min;
for (int i = 0; i < pArray.length; i++) {
min = i;
for (int j = i+1; j < pArray.length; j++) {
if (pArray[j] < pArray[min]) {
min = j;
}
}
swap(pArray, i, min);
}
}
选择排序第二种写法：每次从左向右找出最大的值
/**
* 比较排序，每次记录最大值的位置
*/
private void selectionSortMax(int[] pArray) {
if (pArray == null) {
throw new NullPointerException();
}
int out = pArray.length;
int max = 0;
for (int i = 0; i < pArray.length-1; i++) {
max = 0;
for (int j = 0; j < out; j++) {
if (pArray[j] > pArray[max]) {
max = j;
}
}
out--;
swap(pArray, max, out);
}
}
选择排序第三种写法：每次从右向左找出最大的值
/**
* 比较排序，每次从右向左找出最大的值
*/
private void selectionSortMaxTwo(int[] pArray) {
if (pArray == null) {
throw new NullPointerException();
}
int max;
for (int i = pArray.length-1; i >= 0; i--) {
max = i;
for (int j = 0; j < i; j++) {
if (pArray[j] > pArray[max]) {
max = j;
}
}
if (max != i) {
swap(pArray, i, max);
}
}
}
private void swap(int[] pArray, int pX, int pY) {
int temp = pArray[pX];
pArray[pX] = pArray[pY];
pArray[pY] = temp;
}
main方法：
public static void main(String[] args) {
int[] arr = {3, 5, 1, 10, 0, 100, 3, 9};
SelectionSort selectionSort = new SelectionSort();
selectionSort.selectionSortMin(arr);
selectionSort.selectionSortMax(arr);
for (int i = 0; i < arr.length; i++) {
System.out.println("value = " + arr[i]);
}
}
时间复杂度： n-1 + n-2 + n-3 + ...... + 1 = n(n-1)/2 = O(n^2)
空间复杂度：O(1) 因为未使用辅助空间