排序算法

@Override
protected void onCreate(Bundle savedInstanceState) {
    super.onCreate(savedInstanceState);
    setContentView(R.layout.activity_main);
    int[] ranArr = randomArr(3000, 0, 1000);
    int[] nearlyOrderArr = nearlyOrderArr(10000, 10);
//        int[] bubbleSort = bubbleSort(ranArr);
//        int[] selectionSort = selectionSort(ranArr);
    int[] insertionSort = insertionSort(nearlyOrderArr);
    int[] advanceInsertionSort = advanceInsertionSort(nearlyOrderArr);
//        Log.d("eeeee=ranArr",printArr(ranArr));
}

    //归并排序
public int[] mergeSort(int[] arr,int left,int right){

    if (left>=right)return arr;
    int middle = (left+right)/2;

    //把数组左边归并排序好
    arr = mergeSort(arr, left, middle);
    //把数组右边归并排序好
    arr = mergeSort(arr, middle+1,right);
    //最后两个数组实行归并排序
    recursionMerge(arr,left,middle,right);

    return arr;
}

//归并排序的递归
public int[] recursionMerge(int[] arr,int left,int middle,int right){

    //缓存数组
    int[] cacheArr = new int[right-left+1];
    for (int i = left ;i<=right;i++){
        cacheArr[i-left]=arr[left];
    }

    int i = left; int j = middle+1;
    for (int k = left;k<=right;k++){

        //如果左边的索引已经大于中间值，但是整个归并又还没结束，说明右边剩余的就是整个归并要的顺序了
        if (i>middle){
            arr[k]=cacheArr[j-left];
            j++;
        }
        //如果右边的索引已经大于最大值，但是整个归并又还没结束，说明左边剩余的就是整个归并要的顺序了
        else if (j>right){
            arr[k]=cacheArr[i-left];
            i++;
        }else if (cacheArr[i-left]<cacheArr[j-left]){
            arr[k]=arr[i-left];
            i++;
        }else{
            arr[k]=arr[j-left];
            j++;
        }
    }
    return arr;
}


//随机生成n个元素的数组，并制定范围
public int[] randomArr(int n , int rangeL,int rangeR){
    if (rangeL>rangeR){
        int a = rangeL;
        rangeL=rangeR;
        rangeR=a;
    }
    int[] arr= new int[n];
    Random random = new Random();
    for (int i=0;i<n;i++){
       arr[i]= random.nextInt(rangeR-rangeL+1)+rangeL;
    }
    return arr;
}

//生成近乎有序的数组
public int[] nearlyOrderArr(int n,int swapTimes){
    int[] arr = new int[n];
    for (int i=0;i<n;i++){
        arr[i]=i;
    }
    Random random = new Random();
    for (int j=0;j<swapTimes;j++){
        swap(arr,arr[random.nextInt(n)],arr[random.nextInt(n)]);
    }
    return arr;
}

//冒泡排序
public int[] bubbleSort(int[] arr) {
    long startTime =  System.currentTimeMillis();
    for (int i = 0; i < arr.length - 1; i++) {
        //外循环只需要比较arr.length-1次就可以了
        for (int j = 0; j < arr.length - 1 - i; j++) {
            //-1为了防止索引越界,-i为了提高效率
            if(arr[j] > arr[j+1]) {
                swap(arr,j,j+1);
            }
        }
    }
    long endTime = System.currentTimeMillis();
    Log.d("eeeee=bubble time=",startTime+"=startTime  "+endTime+"=endTime "+(endTime-startTime)+"ms"
    +"  isSorted="+isSorted(arr));
    return arr;
}

//选择排序
public int[] selectionSort(int[] arr){
    long startTime =  System.currentTimeMillis();
    for (int i=0;i<arr.length-1;i++){
        //只需要比较arr.length-1次
        for (int j=i+1;j<arr.length;j++){
            if (arr[j]<arr[i]){
                swap(arr,j,i);
            }
        }
    }
    long endTime = System.currentTimeMillis();
    Log.d("eeeee=selection time=",startTime+"=startTime  "+endTime+"=endTime "+(endTime-startTime)+"ms"
    +"  isSorted="+isSorted(arr));
    return arr;
}

//插入排序
public int[] insertionSort(int[] arr){
    long startTime =  System.currentTimeMillis();
    for (int i=1;i<arr.length;i++){
        //插入排序第一个元素是固定的，只有一个，不用比较，所以i从1开始
        for (int j=i;j>0 && arr[j-1]>arr[j] ;j--){
            swap(arr,j,j-1);
        }
    }
    long endTime = System.currentTimeMillis();
    Log.d("eeeee=insertion time=",startTime+"=startTime  "+endTime+"=endTime "+(endTime-startTime)+"ms"
            +"  isSorted="+isSorted(arr));
    return arr;
}

//高级插入排序
public int[] advanceInsertionSort(int[] arr){
    long startTime =  System.currentTimeMillis();
    for (int i=1;i<arr.length;i++){
        //插入排序第一个元素是固定的，只有一个，不用比较，所以i从1开始
        int a = arr[i];
        int j;
        for (j=i;j>0 && arr[j-1]>a ;j--){
//                swap(arr,j,j-1);
            //交换比较耗时，并且并不一定比前一个要小，当真正小再换
            arr[j]=arr[j-1];
        }
        arr[j]=a;
    }
    long endTime = System.currentTimeMillis();
    Log.d("eeeee=advance insertion",startTime+"=startTime  "+endTime+"=endTime "+(endTime-startTime)+"ms"
            +"  isSorted="+isSorted(arr));
    return arr;
}

//打印数组元素
public String printArr(int[] arr){
    StringBuilder sort= new StringBuilder(" ");
    for (int anArr : arr) {
        sort.append(anArr).append(" ");
    }
    return sort.toString();
}

//交换位置
public void swap(int[] arr,int i,int j ){
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

//判断是否从小到大排序了
public boolean isSorted(int[] arr){
    for (int i=0;i<arr.length-1;i++){
        if (arr[i]>arr[i+1])return false;
    }
    return true;
}