算法入门----排序(选择,冒泡,插排)

1.选择排序

每次从第 i 个开始和它右边每一个比较大小,从i+1一直比到第length-1个,排好的放最左侧,所以 i 每次+1,循环length-1次, i 从0 到 length-2

 /**
     * 选择排序算法
     * @param arr 待排序的整型数组
     */
    //一句话概括: 选择排序 i++~n-1
    //在i~n-1中选出最小的放在i位置上,然后i+1~n-1范围上继续.
    public static void selectionSort(int [] arr){
        if(arr == null || arr.length <2 ){  //null数组，其 length 属性会导致 NullPointerException。
            return;
        }
        int min=0;//最小值索引
        for(int i=0;i<arr.length-1;i++){
            min=i;
            for(int j=i+1;j<arr.length;j++){//选出最小
                if(arr[min]>arr[j]){
                    min=j;
                }
            }
            int temp=arr[min];//交换
            arr[min]=arr[i];
            arr[i]=temp;
        }
        for(int i=0;i<arr.length;i++){
            System.out.println(arr[i]);
        }
    }

2.冒泡排序

每次从 i 开始和 i+1比较, i 向右移动,排好的放右边,所以 i+1每次-1,循环length-1次

//一句话概括: 冒泡排序 i~n--
    //0~i范围上,相邻位置选出较大数,最大值最终来到i位置,然后0~i-1范围上继续
        public static void bubbleSort(int []arr ){
        if(arr ==null || arr.length<2 ){
            return;
        }
        for(int end=arr.length-1;end>0;end--){//length-1~1
            for(int i=0;i<end;i++){
                if(arr[i]>arr[i+1]){
                    int temp=arr[i];
                    arr[i]=arr[i+1];
                    arr[i+1]=temp;
                }
            }
        }
    }

3.插入排序

每次从 j+1(=i) 开始与左侧相邻位置比较, j 左移并与左邻比较 i 次,排好的放左边,循环 length-1次.

//插入排序一句话,0~i-1范围上已经有序,新来的数从右往左滑倒不再小的位置插入,然后继续
    public static void insertSort (int [] arr){
        if(arr == null || arr.length<2){
            return;
        }
        for(int i=1;i<arr.length;i++){
            for(int j=i-1;j>=0;j--){
                if(arr[j+1]<arr[j]){
                    int t=arr[j];
                    arr[j]=arr[j+1];
                    arr[j+1]=t;
                }
            }
        }
    }