Java排序算法

package chaper05;

import java.util.Arrays;

import static MyTools.MyArrayTools.change;

public class ArrayTest01 {
    public static void main(String[]args) {

        int[] arr1= {123,9,453,345,22,56};
        //冒泡排序
        for(int i=arr1.length-1;i>0;i--){
            for(int j=0;j< i;j++) {
                if(arr1[j]>arr1[j+1]) {
                    change(arr1,j,j+1);
                }
            }
        }
        System.out.println(Arrays.toString(arr1));


        int[] arr2= {123,9,453,345,22,56,57,85};
        //选择排序  遍历整个数组,小的改变位置
        for(int i=0;i=0控制的是下标越界问题
            for(int j = i-1;j >= 0 && arr3[j] > arr3[j+1];j--){
                change(arr3,j,j+1);
            }
        }
        System.out.println(Arrays.toString(arr3));

        //归并排序  分治  取中间为基础,分为两个数组,分别将两个数组递归排序
        int[] arr4= {123,9,453,345,22,56,778,98,3590,853};
        int[] arrNew=merger(arr4,0,arr4.length-1);
        System.out.println(Arrays.toString(arrNew));

        //快速排序
        int[] arr5= {123,9,453,345,22,56,778,98,3590,853,5667,67,67};
        int[] arrNew2=quickSort(arr5,0,arr5.length-1);
        System.out.println(Arrays.toString(arrNew2));

    }



     
    public static int[] merger(int[] arr,int l,int r){
        //当l和r相等时,排序无意义,数组长度为1
        if(l == r){
            return new int[]{arr[l]};
        }
        int mid =l + ((r - l)>>1);  //取到中间的下标
        int[] arrLeft=merger(arr,l,mid);
        int[] arrRight=merger(arr,mid+1,r);
        return intoMerger(arr,l,mid,r);
    }
    //然后借助一个临时数组一一比对谁小,谁capy到临时数组中
    private static int[] intoMerger(int[] arr, int l, int m, int r) {
        int[] help = new int[r-l+1];//创建一个临时的帮助数组
        int i = 0;
        int a = l;
        int b = m + 1;
        while(a <= m && b<= r){
            help[i++] = arr[a]<=arr[b] ? arr[a++] : arr[b++];
        }
        //将没有越界的继续拷贝到help数组中,下面的两个while只会有一个执行
        while (a <= m){
            help[i++] = arr[a++];
        }
        while(b<= r){
            help[i++] = arr[b++];
        }
        for (int j=0; j= key) {
                right--;
            }
            //如果没有比基准值小的，则比较下一个，直到有比基准值小的，则交换位置，然后又从前向后比较
            if (arr[right] <= key) {
                change(arr,right,left);
                
            }
            //从前向后比较
            while (left < right && arr[left] <= key) {
                left++;
            }
            //如果没有比基准值大的，则比较下一个，直到有比基准值大的，则交换位置
            if (arr[left] >= key) {
                change(arr,right,left);
                
            }
        }
        //此时第一次循环比较结束，基准值的位置已经确定。左边的值都比关键值小，右边的值都比关键值大，
        // 但是两边的顺序还有可能不一样，接着进行下面的递归调用

        //递归左边序列：从第一个索引位置到“关键值索引-1”
        if (left > low) {
            quickSort(arr,low,left-1);
        }
        //递归右边序列：从“关键值索引+1”到最后一个位置
        if (right < high) {
            quickSort(arr,right+1,high);
        }
        return arr;
    }
}












package MyTools;

public class MyArrayTools {
    
    public static void change(int[] arr , int i, int j){
        int temp=arr[i];
        arr[i]=arr[j];
        arr[j]=temp;
    }
}