常见六种排序算法(java版本)

public static int [] maopao1(int array[]){
    int t;
    for(int i = 0;i <array.length;i ++){
        for(int j = 0;j < array.length-i-1;j ++){
            if(array[j] < array[j+1]){
                t = array[j+1];
                array[j+1] = array[j];
                array[j] = t;
            }
        }
    }
    return array;
}

//选择
    public static int [] selectSort(int[] array){
        int t = 0;
        int max = 0;
        for(int i = 0; i < array.length;i ++){
            max = i;
            for(int j = i;j < array.length;j ++){
                if(array[j] > array[max]){
                    max = j;
                }
            }
            //如果i就是max,不用交换位置
            if(i != max){
                t = array[max];
                array[max] = array[i];
                array[i] = t;
            }
        }
        return array;
    }

//快速排序:分而治之的思想,一左一右两个指针,以left为基准
    public static void quickSort(int left,int right,int [] arr){
        //从小到大排序
        int i = left;
        int j = right;
        //注意:i也不能等于j,当i==j说明排序完成,最后一次的左/右部分只有一个数字
        if(i >= j)
            return ;
        //定义一个基准值
        int k = arr[left];
        while(i != j){
            //i不能大于j
            if(arr[i] <= k && i < j){
                i++;
            }
            if(arr[j] > k && i < j){
                j --;
            }
            if(i < j){
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
        //i == j
        if(k > arr[i]){
            int temp = arr[left];
            arr[left] = arr[i];
            arr[i] = temp;
        }
        //递归
        quickSort(left,i-1,arr);
        quickSort(i,right,arr);
    }

//归并排序:先分割,再合并
    //分割
    public static int [] separate(int [] arr){
        if(arr.length < 2){
            return arr;
        }
        //找中位数,Math.floor(a)得到小于a的最大整数
        //可能数组数量为奇数的情况下
        int mid = (int)Math.floor(arr.length/2);
        //分成两个
        int [] left = Arrays.copyOfRange(arr,0,mid);//(左闭右开]
        int [] right = Arrays.copyOfRange(arr,mid,arr.length);//因为下标从0开始,所以本来就取不到arr.length,不用减一
        //递归
        return merge(separate(left),separate(right));
    }
    //合并
    public static int [] merge(int [] left,int [] right){
        int [] arr = new int[left.length+right.length];
        if(arr.length < 2){
            //判断如果数组长度小于2,那么必定其中一个数组有值,一个无值,返回有值的即可
            return left.length == 0?right:left;
        }
        int i=0,j=0,k=0;
        while(i<left.length && j<right.length){
            //把小的那个数组添加到新数组中
            if(left[i] < right[j]){
                arr[k++] = left[i++];
            }else{
                arr[k++] = right[j++];
            }
        }
        //最后还有一个没有添加到arr新数组中,这时加上去
        while(i < left.length){
            arr[k++] = left[i++];
        }while(j < left.length){
            arr[k++] = right[j++];
        }
        return arr;
    }

public static void insertSortAsc(int [] arr){
        for(int i=1;i<arr.length;i++){
            int temp=arr[i];//temp哨兵位置
            int index=i-1;//index代表与哨兵比较的值的下标
            //index不能小于0&&升序,把index指向的数值与哨兵作比较,如果哨兵小于index指向的元素
            while(index >=0 && arr[index] > temp){
                //把index指向的元素后移一位
                arr[index+1] = arr[index];
                index --;//index--确保从已经排好的元素中选择,从后往前扫描
            }
            //这时,在拍排的序列中,比哨兵大的元素都已在哨兵右边,此时把哨兵放到index+1位置上即可
            arr[index+1] = temp;
        }
    }

public static void shellSortAsc(int[] arr){
        int gap=arr.length/2;//增量,初始为数组长度一半
        while(gap>=1){
            for(int i=gap;i<arr.length;i++){//这里其实就是插入排序,不过把原来的i=1变成i=gap
                int temp=arr[i];
                int index=i-gap;
                while(index>=0&&arr[index]>temp){
                    arr[index+gap]=arr[index];
                    index=index-gap;
                }
                arr[index+gap]=temp;
            }
            gap=gap/2;//增量递减
        }
    }