选择排序：

原理：依次从数组最左边取一个元素，与之后的位置上的元素比較，假设大于/小于(取决于须要升序排还是降序排)。则保存较大/较小元素的索引

当一轮比較后，将保存的较大/较小元素的索引与 这轮開始比較的左边元素置换

改进了冒泡排序，交换次数从O(N^2)降低到O(N), 而比較次数还是O(N^2) 。实际上交换次数最大就等于N-1次

/** * 选择排序 * 比較次数 O(N^2),  交换O(N) * @author stone * */public class SelectionSort {	public static void main(String[] args) {		int len = 15;		int[] ary = new int[len];		Random random = new Random();		for (int j = 0; j < len; j++) {			ary[j] = random.nextInt(1000);		}		System.out.println("-------排序前------");//		ary=new int[]{10,9,8,7,6,5,4,3,2,1}; //測试交换次数//		ary=new int[]{1,2,3,4,5,6,7,8,10,9}; //測试交换次数		for (int j = 0; j < ary.length; j++) {			System.out.print(ary[j] + " ");		}				selectDesc(ary);		selectAsc(ary);	}	/*	 * 选择排序：降序	 */	static void selectDesc(int[] ary) {		int compareCount = 0;//比較次数		int changeCount = 0;//交换次数		int len = ary.length;		int maxValueIndex = -1; //记录一轮比較下来的最小值索引		for (int i = 0; i < len - 1; i++) {			maxValueIndex = i; //从0開始			for (int j = i + 1; j < len; j++) {				if (ary[maxValueIndex] < ary[j]) {					maxValueIndex = j; //记录较大的索引					compareCount++;				}			}//			System.out.println("minValueIndex==" + maxValueIndex);			if (maxValueIndex != i) {//假设跟左边的记录索引不同，则交换				ary[i] = ary[maxValueIndex] + (ary[maxValueIndex] = ary[i]) * 0;//一步交换				changeCount++;			}		}				System.out.println("\n-------降序排序后------比較次数：" + compareCount + "。交换次数" + changeCount);		for (int j = 0; j < ary.length; j++) {			System.out.print(ary[j] + " ");		}	}		/*	 * 选择排序：升序	 */	static void selectAsc(int[] ary) {		int compareCount = 0, changeCount = 0;		int len = ary.length;		int minIndex = -1;		for (int i = 0; i < len - 1; i++) {			minIndex = i;			for (int j = i + 1; j < len; j++) {				if (ary[minIndex] > ary[j]) {					minIndex = j; //记录较小的索引					compareCount++;				}			}			if (minIndex != i) {//假设跟左边的记录索引不同。则交换				ary[i] = ary[minIndex] + (ary[minIndex] = ary[i]) * 0;				changeCount++;			}		}		System.out.println("\n-------升序排序后------比較次数：" + compareCount + "，交换次数" + changeCount);		for (int j = 0; j < ary.length; j++) {			System.out.print(ary[j] + " ");		}	}}

打印

-------排序前------125 350 648 789 319 699 855 755 552 489 187 916 596 731 852 -------降序排序后------比較次数：26，交换次数13916 855 852 789 755 731 699 648 596 552 489 350 319 187 125 -------升序排序后------比較次数：56。交换次数7125 187 319 350 489 552 596 648 699 731 755 789 852 855 916