java常用算法分析和实现（三）

选择排序
简单选择排序
每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。
选择排序不像冒泡排序算法那样先并不急于调换位置，第一轮（k=1）先从array[k]开始逐个检查，看哪个数最小就记下该数所在的位置于minlIndex中，等一轮扫描完毕，如果找到比array[k-1]更小的元素，则把array[minlIndex]和a[k-1]对调，这时array[k]到最后一个元素中最小的元素就换到了array[k-1]的位置。 如此反复进行第二轮、第三轮…直到循环至最后一元素


Java代码
package sort;  
 
import java.util.Comparator;  
 
/** 
* 简单选择排序算法 
* @author jzj 
* @date 2009-12-5 
*  
* @param <E> 
*/ 
public class SelectSort<E extends Comparable<E>> extends Sort<E> {  
 
    /** 
     * 排序算法的实现，对数组中指定的元素进行排序 
     * @param array 待排序的数组 
     * @param from 从哪里开始排序 
     * @param end 排到哪里 
     * @param c 比较器 
     */ 
    public void sort(E[] array, int from, int end, Comparator<E> c) {  
        int minlIndex;//最小索引  
        /* 
         * 循环整个数组（其实这里的上界为 array.length - 1 即可，因为当 i= array.length-1 
         * 时，最后一个元素就已是最大的了，如果为array.length时，内层循环将不再循环），每轮假设 
         * 第一个元素为最小元素，如果从第一元素后能选出比第一个元素更小元素，则让让最小元素与第一 
         * 个元素交换  
         */ 
        for (int i = from; i <= end; i++) {  
            minlIndex = i;//假设每轮第一个元素为最小元素  
            //从假设的最小元素的下一元素开始循环  
            for (int j = i + 1; j <= end; j++) {  
                //如果发现有比当前array[smallIndex]更小元素，则记下该元素的索引于smallIndex中  
                if (c.compare(array[j], array[minlIndex]) < 0) {  
                    minlIndex = j;  
                }  
            }  
 
            //先前只是记录最小元素索引，当最小元素索引确定后，再与每轮的第一个元素交换  
            swap(array, i, minlIndex);  
        }  
    }  
 
    /** 
     * 测试 
     * @param args 
     */ 
    public static void main(String[] args) {  
        Integer[] intgArr = { 5, 9, 1, 4, 1, 2, 6, 3, 8, 0, 7 };  
        SelectSort<Integer> insertSort = new SelectSort<Integer>();  
        Sort.testSort(insertSort, intgArr);  
        Sort.testSort(insertSort, null);  
    }  
}