排序算法(三)--选择排序

 

package sort;

import java.util.Arrays;
import java.util.Random;

/**
 * 选择排序：复杂度N^2
 * 原理： 1.默认从第一个数i开始，假设是最小数，赋值给一个变量tem
 *       2.用而二个开始和这个数比较，如果小于该数，则赋值给这个变量
 *       3.循环第二层循环结束，就交换元素，然后从i++ 开始重复刚才动作
 * 比如：士兵站一排 a,b,c,d,e,f,g 然后从a开始，a:165cm  b:170cm ，记住现在最小的是a,
 *       但是此时并不交换位置，同理c:180cm,a 还是不变位置，循环到后面 g:100cm,
 *       这个时候g 是最矮的，循环结束，a和g  交换位置，其他人的位置都不变，然后从b 开始循环..
 * 分析：相邻比较-交换，把大的往后移，这是冒泡算法，选择排序是冒泡算法的进化版
 *       因为冒泡算法每次比较，符合条件都会交换位置，而选择排序仅仅是先记录位置，一层循环结 *       束才交换
 *  这里这哪是没找到好的图，有了再补上吧！
 * @author @Ran
 * @ AbstractSort 请参考第一篇
 */
public class Selection<T> extends AbstractSort<T> {
	@Override
	public <T extends Comparable<? super T>> T[] sort(T[] t) {
		
		for(int i =0;i<t.length;i++){
			// 默认当前元素为最小值
			T tem = t[i];
			int index = i;
			for(int j=i;j<t.length-1;j++){
				// 和前一个元素比较，如果前一个元素小，则让赋值变量
				if(tem.compareTo(t[j+1])>0){
					index = j+1;
					tem = t[index];
				}
			}
			// 如果当前元素不是最小的，则交换位置
			super.swap(t, i, index);
		}
		return t;
	}
	
	public static void main(String[] args) {
		 int a = 5000;
		 Integer [] t = new Integer[a];
		 Random r = new Random();
		 for(int i =0;i<a;i++){
			 t[i] = r.nextInt(a);
		 }
		 System.out.println("未排序结果："+Arrays.toString(t));
		 // 这里用了下，前面的冒泡算法，做对比
		 Sort s1 = new Bubble();
		 Sort s3 = new Selection();
		 
		 Integer[] t3 = t.clone();
		 
		 s1.sort(s1, t);
		 s3.sort(s3, t3);
		 System.out.println("排序后结果："+Arrays.toString(t3));
		 System.out.println(s1);
		 System.out.println(s3);
	}
}