题解 | #排序#

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 将给定数组排序
     * @param arr int整型一维数组 待排序的数组
     * @return int整型一维数组
     */
    public int[] MySort (int[] arr) {
        // 写三种，快速排序，堆排序和冒泡排序
        //冒泡法O(n*n)
//         bubbleSort(arr,0,arr.length-1);
        //快速排序O(Nlog(N))
//         quickSort(arr,0,arr.length-1);
        //堆排序 O(Nlog(N))
        heapSort(arr);
        return arr;
        
        
    }
    public void swap(int []arr,int i,int j){
           if(i!=j){
               arr[i]^=arr[j];
               arr[j]^=arr[i];
               arr[i]^=arr[j];
           }    
           else
               return ;
    }
    public void bubbleSort(int[] arr,int start,int end){  //轻的先上来
        for(int i=start;i<=end-1;i++){
            for(int j=i+1;j<=end;j++){
                if(arr[i]>=arr[j]){
                    swap(arr,i,j);
                }
            }
        }
    }
    public void quickSort(int []arr,int start,int end){
        if(start<end)  //大于或者等于的话就不用排了，说明只有一个元素或者是第一个元素
        {
            int key=arr[start];   //将第一个作为中枢元素
            int i=start;
            for(int j=i+1;j<=end;j++){
                if(arr[j]<=key){   //小的移动到最靠近目前的元素的地方
                    swap(arr,j,++i);
                }
            }
            arr[start]=arr[i];  //先把位置移出来
            arr[i]=key;
            quickSort(arr,start,i-1);
            quickSort(arr,i+1,end);
        }
    }
    public void heapSort(int[]arr){
        buildMaxHeap(arr,arr.length);
        for(int j=arr.length-1;j>0;j--){
            swap(arr,0,j);
            adjustHeap(arr,0,j);//对0到j（此时为长度）重新调整大顶堆
        }
        
        
    }
    public void buildMaxHeap(int[]arr,int heapSize){
        for(int i=(heapSize-2)/2;i>=0;i--){
            adjustHeap(arr,i,heapSize);
        }
    
    
    
    }
    public void adjustHeap(int[]arr,int i,int heapSize){
        int left=2*i+1;
        int right=2*i+2;
        int largest=i;
        if(left<heapSize&&arr[left]>=arr[largest]){
            largest=left;
        }
        if(right<heapSize&&arr[right]>=arr[largest]){
            largest=right;
        }
        if(largest!=i)//最大的不是父节点了
        {
            swap(arr,i,largest);
            adjustHeap(arr,largest,heapSize);   //交换之后，以原来的子节点作为父节点继续进行调整
        }
        
    }
    
}