排序算法(三)--选择排序
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> {@Overridepublic <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);}}
?
?
