title: 選擇排序算法.md
date: 2017-11-06 20:06:48
tags:

選擇排序

選擇排序（Selection sort）是一種簡單直觀的排序算法一铅。它的工作原理如下。首先在未排序序列中找到最卸橛汀（大）元素潘飘，存放到排序序列的起始位置，然后掉缺，再從剩余未排序元素中繼續(xù)尋找最胁仿肌（大）元素，然后放到已排序序列的末尾眶明。以此類推艰毒，直到所有元素均排序完畢。
選擇排序的主要優(yōu)點與數據移動有關搜囱。如果某個元素位于正確的最終位置上丑瞧，則它不會被移動。選擇排序每次交換一對元素蜀肘，它們當中至少有一個將被移到其最終位置上绊汹，因此對 {\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);

}