选择排序

2019-11-06 06:17:06

字体：大中小

来源：转载

供稿：网友

选择排序

选择排序：每趟从待排序的记录中选出关键字最小的记录，顺序放在已排序的记录序列末尾，直到全部排序结束为止。简单地说，从所有序列中先找到最小的，然后放到第一个位置。之后再看剩余元素中最小的，放到第二个位置……以此类推，就可以完成整个的排序工作了。举个栗子，对5,3,8,6,4这个无序序列进行简单选择排序，首先要选择5以外的最小数来和5交换，也就是选择3和5交换，一次排序后就变成了3,5,8,6,4.对剩下的序列一次进行选择和交换，最终就会得到一个有序序列。写成Comparable<? super T>，而不是Comparable<T>，就可以对任意类型使用Comparable。

public  class Selection_sort {	PRivate static Integer[] data;	public static void main(String[] args) {		Random ra =new Random();		data=new Integer[30];		for(int i=0;i<30;i++)			data[i]=ra.nextInt(100)+1;		display(data);		selectionSort(data);		display(data);	}		public static void display(Integer[] data2) {		for(int i=0;i<data2.length;i++)			System.out.print(data2[i]+" ");		System.out.println();	}		/**	 * 将数组前n个对象升序排序	 * @param a	 * @param n	 */	public static<T extends Comparable<? super T>> void selectionSort(T[] a){		for(int index=0;index<a.length-1;index++){			int indexOfNextSmallest=getIndexOfSmallest(a, index, a.length-1);			swap(a, index, indexOfNextSmallest);		}	}	/**	 * 在数组一部分找出最小值索引	 * @param a	 * @param first	 * @param last	 * @return	 */	private static<T extends Comparable<? super T>> int getIndexOfSmallest(T[] a,int first,int last){		T min=a[first];		int indexOfMin=first;		for(int index=first+1;index<=last;index++){			if(a[index].compareTo(min)<0){				min=a[index];				indexOfMin=index;			}		}		return indexOfMin;	}		private static<T extends Comparable<? super T>> void swap(T[] a,int i,int j){		T temp=a[i];		a[i]=a[j];		a[j]=temp;	}}测试结果12 31 32 20 11 31 21 68 80 93 32 31 61 60 65 70 96 19 86 84 6 71 92 29 92 27 96 14 85 15 6 11 12 14 15 19 20 21 27 29 31 31 31 32 32 60 61 65 68 70 71 80 84 85 86 92 92 93 96 96 选择排序算法性能