/**
 * 选择排序 及其 改进算法 的实现
 * 稳定算法
 * @author 那一季的银杏叶
 *
 */
public class SelectSort {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        new SelectSort().run();
    }
    public void run(){
        int a[] = {3,1,5,7,2,4,9,6};
        /**
         * 选择排序
         */
        selectSort(a);
        /**
         * 选择排序的改进--二元选择排序
         */
        selectTwoSort(a);
    }
    /**
     * 选择排序    每次选出最小的元素
     * @param a
     */
    private void selectSort(int[] a) {
        // TODO Auto-generated method stub
        System.out.println("———————————————————选择排序算法———————————————————");
        int n=a.length;
        for(int i=0;i<n;i++){
            int k=i;
            for(int j=i;j<n;j++){
                if(a[j] < a[k]){
                    k=j;
                }
            }
            if(k != i){
                int temp = a[i];
                a[i]=a[k];
                a[k] = temp;
            }
            print(a,n,i);
        }
        printResult(a,n);
    }
    /**
     * 选择排序的 改进算法
     * 每次选出最大的数和最小的数
     * @param a
     */
    private void selectTwoSort(int[] a){
        System.out.println("———————————————选择排序算法——的改进—————————————————");
        int n=a.length;
        int i,j,max,min,temp;
        for(i=0;i<n/2;i++){
            max=i;
            min=i;
            for(j = i+1;j<n-i;j++){
                if(a[j]<a[min]){
                    min=j;
                }
                if(a[j]>a[max]){
                    max=j;
                }
            }
            temp = a[i];
            a[i] = a[min];
            a[min] = temp;
            
            temp = a[n-i-1];
            a[n-i-1] = a[max];
            a[max] = temp;
            print(a,n,i);
        }
        printResult(a,n);
    }
    /**
     * 打印排序的最终结果
     * @param a
     * @param n
     */
    private void printResult(int[] a, int n){
        System.out.print("最终排序结果：");
        for(int j=0;j<n;j++){
            System.out.print(" "+a[j]);
        }
        System.out.println();
    }
    /**
     * 打印排序的每次循环的结果
     * @param a
     * @param n
     * @param i
     */
    private void print(int[] a, int n, int i) {
        // TODO Auto-generated method stub
        System.out.print("第"+i+"次：");
        for(int j=0;j<n;j++){
            System.out.print(" "+a[j]);
        }
        System.out.println();
    }
}