题解 | 9种排序#排序#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 将给定数组排序
     * @param arr int整型一维数组 待排序的数组
     * @return int整型一维数组
     */
        public int[] MySort(int[] arr) {
//             选择排序
//             return selectSort(arr);
//             冒泡排序
//             return bubbleSort(arr);
//             插入排序
//             return insertSort(arr);
//             希尔排序
//             return shellSort(arr);
//             归并排序
//             return mergeSort(arr,0,arr.length-1);
//             快速排序
//             quickSort(arr,0,arr.length-1);
//             return arr;
//             计数排序
//             return countSort(arr);
//             基数排序
//             return radixSort(arr);
//             桶排序
            return bucketSort(arr);
    }
//     选择排序---选择最小的数与当前数交换
    public int[] selectSort(int[] arr){
        if(arr.length<2)return arr;
        for(int i=0;i<arr.length;i++){
            int min = i;
            for(int j=i+1;j<arr.length;j++){
//                 与当前最小值比
                if(arr[j]<arr[min])min=j;
            }
            swap(arr,i,min);
        }
        return arr;
    }
    
//     冒泡排序---两两比较交换
    public int[] bubbleSort(int[] arr){
        if(arr.length<2) 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 arr;
    }
    
//     插入排序---与当前位置之前的所有元素比
    public int[] insertSort(int[] arr){
        if(arr.length<2)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 arr;
    }
    
//     希尔排序---以间隔分组分别排序，间隔缩短再排序，直至缩短成间隔为1，升级版插入排序
    public int[] shellSort(int[] arr){
//         gap的设定，根据Knuth序列定义，左程云视频
        int h = 1;
        while(h <= arr.length / 3){
            h = h*3 + 1;
        }
        for(int gap =h;gap>0;gap=(gap-1)/3){
            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);
                }
            }
        }
        return arr;
    }
    
//     归并排序---找个中间轴，左边排序好，右边排序好，然后左边右边合并起来，其中每一边排序时再划中间轴，直到相隔两个数进行排序
    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;
    }
//     两个排好序的数组合并，start 左数组起点，end 右数组起点，right 右数组终点
    public void merge(int[] arr,int start,int end,int right){
//         mid为两个有序数组的分界点
        int i = start,j=end,k=0,mid=end-1;
        int[] temp = new int[right-start+1];
        while(i<=mid && j<=right){
            if(arr[i]<=arr[j]){
                temp[k] = arr[i];
                k++;i++;
            }else{
                temp[k] = arr[j];
                k++;j++;
            }
        }
//         剩余数组直接接龙
        while(i<=mid)temp[k++]=arr[i++];
        while(j<=right)temp[k++]=arr[j++];
        
//         赋值原数组
        for(int m=0;m<k;m++){
            arr[start+m] = temp[m];
        }
    }
    
//     快速排序---选择中轴数，左边向右，右边向左，分别与中轴数比较，大小交换，中轴数与左指针交换，左边递归，右边递归
    public void quickSort(int[] arr,int left,int right){
        if(left >= right) return ;
        int pivot = arr[left];
        int i = left,j = right;
        while(i < j){
            while(arr[j] >= pivot && j>i){
                j--;
            }
            while(arr[i] <= pivot && i<j){
                i++;
            }
            if(i < j){
                swap(arr,i,j);
            }
        }
        swap(arr,left,i);
        //左子数组
        quickSort(arr,left,j-1);
        //右子数组
        quickSort(arr,j+1,right);
    }
    
//     计数排序---不适合，数据量比数据范围小
    public int[] countSort(int[] arr){
        int[] newArr = new int[arr.length];
        int[] countArr = new int[6];
        for(int i=0;i<arr.length;i++){
            countArr[arr[i]]++;
        }
        for(int i=1,j=0;i<countArr.length;i++,j++){
            while(countArr[i]--!=0){
                newArr[j++]=i;
            }
        }
        return newArr;
    }
    
//     基数排序---二维数组，10*数组长度，从个位数一直到最大位数，分别排序重组
    public int[] radixSort(int[] arr){
//         找到最大位数
        int max = 1;
        for(int i=0;i<arr.length;i++){
            int count = 1;
            int temp = arr[i];
            while(temp/10>0){count++;temp = temp/10;}
            if(count>max)max = count;
        }
        
        for(int m=0;m<max;m++){
            int[][] countArr = new int[10][arr.length];
            for(int i=0;i<arr.length;i++){
                int n = m;
                int temp = arr[i];
                while(n-->0){temp=temp/10;}
                int result = temp%10;
                for(int k=0;k<countArr[result].length;k++){
                    if(countArr[result][k]==0){
                        countArr[result][k]=arr[i];
                        break;
                    }
                }
            }
            //         重组数组
            arr = reGroup(countArr,arr.length);
        }
        return arr;
    }
//     重组数组
    public int[] reGroup(int[][] countArr,int length){
        int[] arr = new int[length];
        int k=0;
        for(int i=0;i<countArr.length;i++){
            for(int j=0;j<countArr[i].length;j++){
                if(countArr[i][j]>0){
                    arr[k++] = countArr[i][j];
                }
            }
        }
        return arr;
    }
    
//     桶排序---给定n个桶，找到最大数与最小数，计算出每个桶能装的数的范围，将数分别放入符合条件的桶中，对每个桶进行快速排序，最后合并
    public int[] bucketSort(int[] arr){
//         设置桶的个数
        int bucket = 4;
//         找到数组中的最大最小值
        int min = arr[0],max=arr[0];
        for(int i=0;i<arr.length;i++){
            if(arr[i]>max)max=arr[i];
            if(arr[i]<min)min=arr[i];
        }
//         每个桶盛数的范围
        int range = (max-min)/bucket;
        int[][] newArr = new int[bucket][arr.length];
        for(int i =0;i<arr.length;i++){
            int temp = arr[i];
            if(temp >= min && temp < min+range){
                for(int k =0;k<newArr[0].length;k++){
                    if(newArr[0][k]==0){
                        newArr[0][k] = arr[i];
                        break;
                    }
                }
            }
            if(temp >= min+range && temp < min+2*range){
                for(int k =0;k<newArr[0].length;k++){
                    if(newArr[1][k]==0){
                        newArr[1][k] = arr[i];
                        break;
                    }
                }
            }
            if(temp >= min+2*range && temp < max - range){
                for(int k =0;k<newArr[0].length;k++){
                    if(newArr[2][k]==0){
                        newArr[2][k] = arr[i];
                        break;
                    }
                }
            }
            if(temp >= max - range && temp <= max){
                for(int k =0;k<newArr[0].length;k++){
                    if(newArr[3][k]==0){
                        newArr[3][k] = arr[i];
                        break;
                    }
                }
            }       
        }
//         对每个桶进行排序
        for(int i=0;i<newArr.length;i++){
            quickSort(newArr[i],0,newArr[i].length-1);
        }
//         重组数组
        return reGroup(newArr,arr.length);
    }
        
    
//     交换位置
    public void swap(int[] arr,int i,int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}