排序之选择排序

选择排序

 选择排序 观其名，识其意。和冒泡一样通过嵌套循环将数组所有对象扫描一遍，选择最小（最大）的对象，
 将其置换至对应的位置（a[0]/a[length-1]）.
 
 这里可以将排序的过程看做两个步骤。
 1 循环扫描数组，选择当前最小的对象并且记录其位置。
 2 将最小的对象置换至对应的位置上。

 

class Sort{
	private long[] a;
	private int nElement;
	public Sort(long[] array){
		this.a = array;
	}
	
	
	public static void main(String[] args) {
		long[] array = new long[]{5,3,1,7,9,2,0};
		Sort b = new Sort(array);
		b.selectSort();
		System.out.println(b);
	}
	
		
	//选择排序
	public void selectSort(){
		int out,in,low;
		int step = 0;
		for(out = 0; out < a.length; out++){
			low = out;//low 记录当前最小对象的位置。初始化指向起始的比较对象，
			
			//同冒泡一样，遍历比较数组中所有的对象。并且记录最小当前
			//最小对象的位置。
			for(in = out + 1; in < a.length; in++){
				if(a[low] > a[in]){
					low = in;
				}
			}
			//将当前对象对象置换至当前排序中对应的位置。
			if(low != out){
				long temp = a[out];
				a[out] = a[low];
				a[low] = temp;
				step ++;
			}
		}
		System.out.println("step = "+step);
	}

	public String toString(){
		StringBuilder b = new StringBuilder();
		for(long l : a){
			b.append(l);
			b.append(",");
		}
		return b.toString();
	}
}

 

 选择排序同样进行了 21 次比较（N*（N-1）/ 2） 但只对数组进行了5 次操作，
 （同数组，冒泡操作了13次）。时间一样，效率高于冒泡排序