アルゴリズム-積み上げ順序、快速列-最小K個数、そして並べ替え出力

class Solution {
    // 1.     ，    k  
    // 2.             
    public int[] smallestK(int[] arr, int k) {
        if(arr == null || arr.length == 0 || k<=0){
            return new int[0];
        }
        int start;

        //      
        int heapSize = arr.length < k ? arr.length : k;
        
        //     
        if(heapSize % 2 == 0){
            start = heapSize/2 - 1;
        }else{
            start = heapSize/2;
        }

        //               ，               
        for(; start >= 0; start--){
            adjustMaxHeap(arr, start, heapSize);
        }


        //             ，   heap+1           ，
        //        ；                   
        if(heapSize<arr.length){
            int tmp = 0;
            for(int i = heapSize;i<arr.length;i++){
                if(arr[i]<arr[0]){
                    tmp = arr[0];
                    arr[0] = arr[i];
                    arr[i] = tmp;
                    adjustMaxHeap(arr,0,heapSize);
                }
            }
        }
        
        //       ，          k    ，        k  
        //            :          ，          （         ）
        for(int i = 0 ; i < heapSize; i++){
            int tmp = arr[0];
            arr[0] = arr[heapSize-i-1];
            arr[heapSize-i-1] = tmp;
            adjustMaxHeap(arr,0,heapSize-i-1);
        }

        //                 ，   
        int[] result = new int[heapSize];
        for(int i = 0; i<heapSize; i++){
            result[i] = arr[i];
        }
        return result;
    }

    public void adjustMaxHeap(int arr[], int start, int length){
        if(length<0){
            return;
        }
        //      
        int tmp = arr[start];
        //               ，         
        //                。            ，     
        for(int j = (start+1)*2 -1 ; j<length; j = (start+1)*2 -1 ){
            //       j   
            if(j < length){
                //          ，              
                if(j+1 < length){
                    j = arr[j] > arr[j+1] ? j : j + 1;
                }
                //              ，            
                if(tmp > arr[j]){
                    break;
                }
                //             
                arr[start] = arr[j];
                //                      
                start = j;
            }
        }
        //     ，start        
        arr[start] = tmp;
    }
}

class Solution {
    //         ，         ，
    //           K  ，       k  
    public int[] getLeastNumbers(int[] arrs, int k) {
        //   
        quickSort(arrs, 0, arrs.length-1, k);
        //     k         
        int[] result = new int[k];
        for(int i = 0; i < k; i++){
            result[i] = arrs[i];
        }
        return result;
    }
    //       ,k      k      
    public void quickSort(int[] arrs, int low, int high, int k){
        if(low >= high){
            //             ，    
            return;
        }
        //       
        int tmp = arrs[low];
        int i = low,j=high;
        while(i<j){
            //  high       ，         ，             
            while(i<j&&arrs[j]>tmp){
                j--;
            }
            if(i<j){
                //                   ，    i  +1
                //     j          ，                    
                arrs[i++] = arrs[j];
            }
            //   ，              ，        
            while(i<j&&arrs[i]<=tmp){
                i++;
            }
            if(i<j){
                arrs[j--] = arrs[i];
            }
        }
        //   ，i==j，                            
        //               
        arrs[i] = tmp;
        if(i + 1 - low < k){
            //         k，            k-(i + 1 - low)      ，    
            quickSort(arrs, i+1, high, k-(i + 1 - low));
        } else if(i + 1 - low > k){
            //         k，            k      ，    
            quickSort(arrs, low, i-1, k);
        }
    }
}