算法小记：选择排序

一、概念

• 选择排序（它在不断的选择剩余元素之中的最小者）：首先，找到数组中最小的那个元素，其次，将它和数组的第一个元素交换位置（如果第一个元素就是最小元素那么它就和自己交换）。再次，在剩下的元素中找到最小元素，将它与数组的第二个元素交换。如此往复，直道将整个数组排序；

  二、特点

  • 运行时间与输入无关：找出最小的元素而扫描一遍数组并不能为下一遍扫描提供什么信息；

  • 数据移动是最少的：交换的次数和数组的大小是线性关系；

    四、代码

    /** 
     * 选择排序 
     *  
     * @author pengcx 
     *  
     */ 
    public class Selection { 
     
        public static void main(String[] args) { 
            String[] a = { "d", "a", "w", "b", "q" }; 
            Selection.sort(a);  
            show(a); 
        } 
     
        /**  
        * 排序数组a 
        *  
        * @param a 
        *            排序的数组a 
        */ 
        public static void sort(Comparable[] a) { 
        int N = a.length; 
        for (int i = 0; i < N; i++) { 
            // 默认最小元素为a[i] 
            int min = i; 
            // 从a[i+1]至a[N]中寻找到最小元素 
            for (int j = i + 1; j < N; j++) { 
                // 如果a[j]比a[min]小，则当前最小元素为a[j] 
               if (less(a[j], a[min])) { 
                   min = j; 
                } 
            } 
            // 将a[min]于a[i]交换 
            exch(a, i, min); 
        } 
    } 
     
        /** 
        * 交换数组a中的第i个元素和第j个元素 
        *  
        * @param a 
        *            交换元素的数组a 
        * @param i 
        *            交换元素的索引i 
        * @param j 
        *            交换元素的索引j 
        */ 
        private static void exch(Comparable[] a, int i, int j) { 
            Comparable swap = a[i]; 
            a[i] = a[j]; 
            a[j] = swap; 
        } 
     
        /** 
        * 比较v和w的大小 
        *  
        * @param v 
        *            比较的元素v 
        * @param w 
        *            比较的元素w 
        *  @return 大小标识 
        */ 
        private static boolean less(Comparable v, Comparable w) { 
            return (v.compareTo(w) < 0); 
        } 
     
        private static void show(String[] a) { 
            for (int i = 0; i < a.length; i++) { 
            System.out.print(a[i]); 
            } 
        } 
    }