排序算法-选择排序

选择排序
基本思路：从所有元素中选择一个最小元素a[i]放在a[0]（即让最小元素a[i]与a[0]
交换），作为第一轮；第二轮是从a[1]开始到最后的各个元素中选择一个最小元素，放在a[1]中；……依次类推。n个数要进行（n－1）轮。

算法对比：

冒泡排序：比较的次数与冒泡法一样多，但是在每一轮
      中只进行一次交换，比冒泡法的交换次数少，相对于冒泡法效率高。

插入排序：相对与插入排序来说，选择排序每次选出的都是全局第i小的，不会调整前i个元素了。

 

在这里补充一下，前面两个的一个基础类：

package com.zenoh.algorithms;

public abstract class Sorter<T extends Comparable<T>> {

	/**
	 * 排序算法函数
	 * 
	 * @param array
	 *            数组
	 * @param from
	 *            开始
	 * @param len
	 *            长度
	 */
	public abstract void sort(T[] array, int from, int len);

	public final void sort(T[] array) {
		sort(array, 0, array.length);
	}

	/**
	 * 交换数组的两个元素
	 * @param array
	 * @param from
	 * @param to
	 */
	protected final void swap(T[] array, int from, int to) {
		T tmp = array[from];
		array[from] = array[to];
		array[to] = tmp;
	}

}

 

public class SelectSorter<T extends Comparable<T>> extends Sorter<T> {

	/**
	 * 选择排序
	 */
	@Override
	public void sort(T[] array, int from, int len) {
		 for(int i=0;i<len;i++)
	        {
	            int smallest=i;
	            int j=i+from;
	            for(;j<from+len;j++)
	            {
	                if(array[j].compareTo(array[smallest])<0)
	                {
	                    smallest=j;
	                }
	            }
	            swap(array,i,smallest);
	                   
	        }

	}

	
	/**
	 * 测试	
		 * @param args
		 */
		public static void main(String[] args) {
			Integer array[] = {2,35,5,78,1,90,13,56} ;
			for (int i = 0 ; i<array.length ; i++){
				System.out.print(array[i]+",");
			}
			System.out.println();
			Sorter sorter = new SelectSorter<Integer>() ;
			sorter.sort(array) ;
				
			for (int i = 0 ; i<array.length ; i++){
				System.out.print(array[i]+",");
			}				
			}
}