题解 | #排序#最小的K个数

import java.util.*;

public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
//         冒泡排序
//         int[] arr = bubbleSort(input,k);
//         插入排序
//         int[] arr = insertSort(input,k);
//         希尔排序
//         int[] arr = shellSort(input,k);
//         归并排序
//         int[] arr = mergeSort(input,k);
//         快速排序
        int[] arr = quickSort(input,k);
//         计数排序
//         int[] arr = countSort(input,k);
//         基数排序---有0不行
//         int[] arr = radixSort(input,k);
        return arrToList(arr);
    }
//     冒泡排序
    public int[] bubbleSort(int[] arr,int k){
        if(arr.length<k)return new int[1];
        if(arr.length==k)return arr;
        for(int i=0;i<arr.length;i++){
            for(int j=i+1;j<arr.length;j++){
                if(arr[i]>arr[j])swap(arr,i,j);
            }
        }
        return cutArray(arr,k);
    }
    
//     插入排序
    public int[] insertSort(int[] arr,int k){
        if(arr.length<k)return null;
        if(arr.length==k)return arr;
        for(int i =1;i<arr.length;i++){
            for(int j = i;j>0;j--){
                if(arr[j]<arr[j-1])swap(arr,j,j-1);
            }
        }
        return cutArray(arr,k);
    }
    
//     希尔排序
    public int[] shellSort(int[] arr,int k){
        if(arr.length<k)return null;
        if(arr.length==k)return arr;
//         设置间隔
        int gap=1;
        while(gap<arr.length/3){
            gap = gap*3+1;
        }
        
        while(gap>0){
            for(int i=gap;i<arr.length;i++){
                for(int j=i;j-gap>=0;j=j-gap){
                    if(arr[j]<arr[j-gap])swap(arr,j,j-gap);
                }
            }
            //缩短间隔
            gap=(gap-1)/3;
        }
        
        return cutArray(arr,k);
    }

//     归并排序
    public int[] mergeSort(int[] arr,int k){
        if(arr.length<k)return null;
        if(arr.length==k)return arr;
        mergesort(arr,0,arr.length-1);
        return cutArray(arr,k);
    }
    
    public int[] mergesort(int[] arr,int left,int right){
        if(left>=right)return arr;
        int mid = left+(right-left)/2;
        mergesort(arr,left,mid);
        mergesort(arr,mid+1,right);
        merge(arr,left,mid+1,right);
        return arr;
    }
    public void merge(int[] arr,int leftPr,int rightPr,int end){
        int i=leftPr,j=rightPr,k=0;
        int[] temp = new int[end-leftPr+1];
        while(i<=rightPr-1 && j<=end){
            if(arr[i]<=arr[j]){
                temp[k++] = arr[i++];
            }else{
                temp[k++] = arr[j++];
            }   
        }
//         剩余数组接龙
        while(i<rightPr)temp[k++] = arr[i++];
        while(j<=end)temp[k++] = arr[j++];
        
//         还原
        for(int m=0;m<temp.length;m++){
            arr[leftPr+m]=temp[m];
        }
    }
    
//     快速排序
    public int[] quickSort(int[] arr,int k){
        if(arr.length<k)return null;
        if(arr.length==k)return arr;
        quicksort(arr,0,arr.length-1);
        return cutArray(arr,k);
    }
    public void quicksort(int[] arr,int left,int right){
        if(left>=right)return;
        int pirot = arr[left];
        int i=left,j=right;
        while(i<j){
            while(arr[j]>=pirot && i<j)j--;
            while(arr[i]<=pirot && i<j)i++;
            if(i<j)swap(arr,i,j);
        }
        swap(arr,i,left);
        quicksort(arr,left,j-1);
        quicksort(arr,j+1,right);
    }
    
//     计数排序
    public int[] countSort(int[] arr,int k){
        if(arr.length<k)return null;
        if(arr.length==k)return arr;
//         计数数组
        int[] count = new int[1000];
        int[] newArr = new int[arr.length];
        for(int i:arr){
            count[i]++;
        }
        int m = 0;
        for(int i=0;i<count.length;i++){
            while(count[i]--!=0)newArr[m++]=i;
        }
        return cutArray(newArr,k);
    }
    
//     基数排序
    public int[] radixSort(int[] arr,int k){
        if(arr.length<k)return null;
        if(arr.length==k)return arr;
//         获取最大位数
        int max = 1;
        for(int i=0;i<arr.length;i++){
            int count = 1,temp = arr[i];
            while(temp/10>0){
                temp=temp/10;
                count++;
            }
            if(count>max)max=count;
        }
        
        
        for(int i=0;i<max;i++){
//         定义二维数组
            int[][] radix = new int[10][arr.length];
            for(int j=0;j<arr.length;j++){
                int temp = arr[j];
                int n = i;
                while(n-->0){
                    temp=temp/10;
                }
                int result = temp%10;
                for(int m=0;m<radix[result].length;m++){
                    if(radix[result][m]==0){
                        radix[result][m]=arr[j];
                        break;
                    }
                }
            }
            arr = reGroup(radix,arr.length);
        }
        return cutArray(arr,k);
    }
    
//     重排二维数组
    public int[] reGroup(int[][] count,int length){
        int[] arr = new int[length];
        int k = 0;
        for(int i=0;i<count.length;i++){
            for(int j=0;j<count[i].length;j++){
                if(count[i][j]!=0)arr[k++] = count[i][j];
            }
        }
        return arr;
    }
    
//     截取数组
    public int[] cutArray(int[] arr,int k){
        int[] newArr = new int[k];
        int m=0;
        for(int i=0;i<k;i++)newArr[m++]=arr[i];
        return newArr;
    }
    
//     数组转列表
    public ArrayList<Integer> arrToList(int[] arr){
        ArrayList<Integer> list = new ArrayList<Integer>();
        for(int i=0;i<arr.length;i++)list.add(arr[i]);
        return list;
    }
    
//     交换数组中两个位置的值
    public void swap(int[] arr,int i,int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}