选择排序——直接选择排序

选择排序：每一趟从待排序的记录里选取关键字最小的记录，顺序放在已经排好序的子文件最后，直到全部记录排序完毕，

一、直接选择排序

1.基本思想：

第一次从R[0]~R[n-1]中选取最小值，与R[0]交换，第二次从R[1]~R[n-1]中选取最小值，与R[1]交换，....，第i次从R[i-1]~R[n-1]中选取最小值，与R[i-1]交换，.....，第n-1次从R[n-2]~R[n-1]中选取最小值，与R[n-2]交换，总共通过n-1次，得到一个按排序码从小到大排列的有序序列。

2.java实现：

	public void selectSort(int[] a) {
		int len=a.length;
		//进行n-1次选择
		for(int i=0;i<len-1;i++) {
			int min=a[i];
			int minIndex=i;//最小值的下标
			for(int j=i+1;j<len;j++) {
				if(a[j]<a[i]) {
					min=a[j];
					minIndex=j;
				}
			}
			//将找到的最小值与i位置元素交换
			if(min!=i) {
				int temp=a[i];
				a[i]=a[minIndex];
				a[minIndex]=temp;
			}
		}
	}

3.算法分析

关键字比较次数：共需要进行n-1次选择，每次选择需要进行 n-i 次比较 (1<=i<=n-1)，总的比较次数为n(n-1)/2

记录移动次数：初始为正序时移动为0；反序每趟都要进行交换操作，总的移动次数为3(n-1)

直接选择排序的时间复杂度为 O(n^2) ，所以当记录占用字节数较多时，通常比直接插入排序的执行速度快些。

由于在直接选择排序中存在着不相邻元素之间的互换，因此，直接选择排序是一种不稳定的排序方法。