算法之选择排序/JAVA

0.0 选择排序

算法思想：选择排序，顾名思义是一种通过选择进行排序的算法。其实质是：第一次遍历数组，找到最小的元素和第一个元素互换，然后第二次遍历数组，找到第二小的元素，和第二个元素进行互换。值得注意的是，当我们第二次遍历数组时，如果第二个元素就是最小的，那么他也会和自己进行互换，所以选择排序的运行时间和输入无关。所以当我们输入一个同样长的已经排好序的数组和一个乱序数组的排序时间一样。

特点：

• 移动数据少
• 算法所耗时间与数组大小是线性关系
• 时间复杂度：O(N^2)

算法实现（只给出sort方法）

ublic class Selection {
    /**
     * 具体算法实现
     */
    public static void sort(Comparable[] a) {
        //遍历数组长度
        for (int i = 0; i < a.length; i++) {
            //假设当前最小
            int min =i;
            //遍历j寻找是否有比当前数组(a[min])还小的数组
            for (int j = i+1; j <a.length ; j++) {
                //比较
                if (less(a[j],a[min])) {
                    min = j;
                }
            }
            //当前数组和最小的数组进行互换
            exch(a,i,min);
        }
    }

    /**
     * 对两个元素进行比较，如果v<w返回true
     * @param v
     * @param w
     * @return
     */
    private static boolean less(Comparable v ,Comparable w){
        /**
         * compareTo 方法
         * 返回为正数表示v>w, 返回为负数表示v<w, 返回为0表示v==w
         */
        return v.compareTo(w) < 0;
    }

    /**
     * 交换a[i]和a[j]
     * @param a
     * @param i
     * @param j
     */
    private static void exch(Comparable[] a, int i, int j){
        Comparable t = a[i];
        a[i] = a[j];
        a[j] = t;
    }

    /**
     * 输出数组
     * @param a
     */
    private static void show(Comparable[] a){
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i] + " ");
        }
        System.out.println();
    }

    /**
     * 测试数组是否有序
     * @param a
     * @return
     */
    private static boolean isSort(Comparable[] a){
        for (int i = 0; i < a.length; i++) {
            if (less(a[i],a[i-1])) {
                return false;
            }
        }
        return true;
    }

    /**
     * 主函数
     * @param args
     */
    public static void main(String[] args) {
        String[] a = {"5","3","6","5","7","9","2","1","3","8"};
        sort(a);
        assert isSort(a);
        show(a);
    }

}