选择排序

选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
选择排序的主要优点与数据移动有关。如果某个元素位于正确的最终位置上，则它不会被移动。选择排序每次交换一对元素，它们当中至少有一个将被移到其最终位置上，因此对 {\displaystyle n} n个元素的表进行排序总共进行至多 {\displaystyle n-1} {\displaystyle n-1}次交换。在所有的完全依靠交换去移动元素的排序方法中，选择排序属于非常好的一种。维基百科

代码实现如下

package cai.suanfa;

/**
 * Created by caiyl on 2017/11/5.
 * 选择排序
 */
public class SelectSort extends TempSort{

    private Integer[] arr = {9,2,1,7,3,8};

    public static void main(String[] args) {
        SelectSort selectSort = new SelectSort();
        selectSort.sort(selectSort.arr);
        selectSort.show(selectSort.arr);
    }

    @Override
    public void sort(Comparable[] arr) {

        for (int i = 0; i < arr.length; i++) {
            int min = i;
            for (int j = i+1; j < arr.length; j++) {
                if (isLess(arr[j],arr[min])) {
                    min = j;//找出最小元素的位置
                }
            }
            exch(arr,i,min);//交换
        }

    }

}

package cai.suanfa;

/**
 * Created by caiyl on 2017/11/5.
 */
public abstract class  TempSort {

    /**
     * 打印排序过的数据
     * @param arr
     */
    public void show(Comparable [] arr) {
        for (int i = 0; i < arr.length; i++) {
            System.out.println(arr[i]);

        }
    }

    /**
     * v1是否小于v2
     * @param v1
     * @param v2
     * @return
     */
    public boolean isLess(Comparable v1, Comparable v2){
        return v1.compareTo(v2) < 0;
    }
    /**
     * v1是否大于v2
     * @param v1
     * @param v2
     * @return
     */
    public boolean isGreater(Comparable v1, Comparable v2){
        return v1.compareTo(v2) > 0;
    }

    public void exch(Comparable[] arr,int i, int j){
        Comparable temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    protected  abstract void sort(Comparable[] arr);

}