package com.hsm.mySort;

import java.util.Random;

/**
 * 排序
 * @author steven
 *
 */
public class MySort {
    public static void main(String[] args) {
        Random rd=new Random();
        int a[]=new int[100];
        for(int i=0;i<100;i++){
            a[i]=rd.nextInt(1000);
        }
        //bubbleSort(a);
        //insertSort(a);
        //shellSort(a);
        selectSort(a);
    }
    /**
     * 冒泡排序
     * @param a
     */
    static void bubbleSort(int [] a){
        int temp=0;//临时交换
        for(int i=0;i<a.length;i++){//遍历
            boolean flag=false;//标识有没有交换
            for(int j=i+1;j<a.length;j++){
                if(a[i]>a[j]){
                    temp=a[i];
                    a[i]=a[j];
                    a[j]=temp;
                    flag=true;
                }
            }
            if(flag) break;//没有交换元素表明已经是有序的了
        }
        for (int i : a) {//输出排好序的元素
            System.out.println(i);
        }
    }
    /**
     * 插入排序
     * @param a
     */
    static void insertSort(int [] a){
        int temp=0;//临时交换
        int j=0;
        for(int i=1;i<a.length;i++){//遍历
            temp=a[i];
            for(j=i;j>0&&a[j-1]>temp;j--){//将元素往后移
                a[j]=a[j-1];
            }
            a[j]=temp;//将元素插入到正确的位置
        }
        for (int i : a) {//输出排好序的元素
            System.out.println(i);
        }
    }
    /**
     * 希尔排序
     * @param a
     */
    static void shellSort(int [] a){
        int temp=0;
        int j;
        for(int d=a.length/2;d>0;d/=2){//间隔每次为原来的1/2
            for(int i=0;i<a.length/d;i++){//这个地方其实就是插入排序
                temp=a[i];
                for(j=i;j>=d&&a[j-d]>temp;j-=d){//将元素往后移
                    a[j]=a[j-d];
                }
                a[j]=temp;//将元素插入到正确的位置
            }
        }
        for (int i : a) {//输出排好序的元素
            System.out.println(i);
        }
    }
    /**
     * 选择排序
     * @param a
     */
    static void selectSort(int [] a){
        int temp=0;//记录最小值的位置
        int temp2=0;
        for(int i=0;i<a.length;i++){//遍历
            boolean flag=false;//标识有没有交换
            for(int j=i;j<a.length;j++){
                if(a[j]<a[temp]){
                    temp=j;
                }
            }
            if(flag) break;//没有交换元素表明已经是有序的了
            temp2=a[i];
            a[i]=a[temp];
            a[temp]=temp2;
        }
        for (int i : a) {//输出排好序的元素
            System.out.println(i);
        }
    }
}