题解 | #排序#

总结：
排序查找问题最常用的几种排序，需要掌握：冒泡排序，快速排序，归并排序，堆排序，以及折中查找。

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 将给定数组排序
     * @param arr int整型一维数组 待排序的数组
     * @return int整型一维数组
     */
    public int[] tmp;
    public int[] MySort (int[] arr) {
        // write code here
        //冒泡
//         int len = arr.length;
//         for(int i=0;i<len-1;i++)
//             for(int j=len-1;j>i;j--){
//                 if(arr[j-1]>arr[j]){
//                     int temp = arr[j];
//                     arr[j] = arr[j-1];
//                     arr[j-1]=temp;
//                 }
//             }
//         return arr;

        //快排
//         QuickSort(arr,0,arr.length-1);
//         return arr;

        //归并排序
        tmp = new int[arr.length];
        MergeSort(arr,0,arr.length-1);
        return arr;

        //堆排序
//         HeapSort(arr,arr.length);
//         return arr;
    }
    public  void MergeSort(int[] arr,int low,int high){
        if(low<high){
            int mid = low+(high-low)/2;
            MergeSort(arr,low,mid);
            MergeSort(arr,mid+1,high);
            Merge(arr,low,mid,high);
        }
    }
    public  void Merge(int[] arr,int low,int mid,int high){
        for(int i=low;i<=high;i++)
            tmp[i] = arr[i];
        int i,j,k;
        for(i=low,j=mid+1,k=i;i<=mid&&j<=high;k++){
            if(tmp[i]<=tmp[j])
                arr[k] = tmp[i++];
            else
                arr[k]=tmp[j++];
        }
        while(i<=mid) arr[k++] = tmp[i++];
        while(j<=high) arr[k++] = tmp[j++];
    }
    public  void QuickSort(int[] arr,int low,int high){
        if(low<high){
            int pivotpos = Partition(arr,low,high);
            QuickSort(arr,low,pivotpos-1);
            QuickSort(arr,pivotpos+1,high);
        }
    }
    public  int Partition(int[] arr,int low,int high){
        int pivot = arr[low];
        while(low<high){
            while(low<high&&arr[high]>=pivot) high--;
            arr[low] = arr[high];
            while(low<high&&arr[low]<=pivot) low++;
            arr[high] = arr[low];
        }
        arr[low] = pivot;
        return low;
    }
    //堆排序
    public  void HeapSort(int[] arr,int len){
        BuildMaxHeap(arr,len);//建初始堆
        for(int i=len-1;i>0;i--){
            int tmp = arr[i];
            arr[i] = arr[0];
            arr[0] = tmp;
            HeapAdjust(arr,0,i);
        }
    }
    public  void BuildMaxHeap(int[] arr,int len){
        for(int i=len/2-1;i>=0;i--){
            HeapAdjust(arr,i,len);
        }
    }
    public  void HeapAdjust(int[] arr,int k,int len){
        int tmp = arr[k];
        for(int i=2*k+1;i<len;i=i*2+1){
            if((i<len-1)&&arr[i]<arr[i+1])
                i++;
            if(arr[i]>tmp){
                arr[k] = arr[i];
                k=i;
            }else
                break;


        }
         arr[k] = tmp;   
    }
}