快速排序

Random r=new Random();
    public int findKethLargest(int[] nums,int k){
        return quickSort(nums,0,nums.length-1,nums.length-k);
    }

    public int quickSort(int[] nums,int left,int right,int position){
        //获取对应的下一个位置
        int index=getIndex(nums,left,right);
        if(index==position){
            return nums[index];
        }else{
            //进行递归
            return index<position? quickSort(nums,index+1,right,position):quickSort(nums,left,index-1,position);
        }
    }

    public int getIndex(int[] nums,int left,int right){
//        int tmp=nums[left];
        //通过随机的方式获得主元位置
        int pos=r.nextInt(right-left+1)+left;
        int tmp=nums[pos];
        nums[pos]=nums[left];
        nums[left]=tmp;
        while(left<right){
            while(left<right&&nums[right]>=tmp){
                right--;
            }
            nums[left]=nums[right];
            while(left<right&&nums[left]<=tmp){
                left++;
            }
            nums[right]=nums[left];
        }
        nums[left]=tmp;
        return left;
    }

堆排序

    public int findKthLargest(int[] nums,int k){
        int heapSize=nums.length;
        buildHeap(nums,heapSize);
        //堆的删除
        for(int i=0;i<k-1;i++){
            //每次删除将第一个元素与最后元素交换
            swap(nums,nums.length-i-1,0);
            heapSize--;
            heapify(nums,0,heapSize);
        }
        return nums[0];
    }

    public void buildHeap(int[] nums,int heapSize){
        //创建堆需要对每一个非叶节点调整
        for(int i=heapSize/2-1;i>=0;i--){
            heapify(nums,i,heapSize);
        }
    }

    //将以i为根节点的子树进行调整
    public void heapify(int[] nums,int root,int heapSize){
        int left=root*2+1;int right=root*2+2;
        int largest=root;
        //获取最大的节点数组下标
        if(left<heapSize&&nums[left]>nums[largest]){
            largest=left;
        }
        if(right<heapSize&&nums[right]>nums[largest]){
            largest=right;
        }
        //进行交换
        if(largest!=root){
            swap(nums,largest,root);
            //递归调整
            heapify(nums,largest,heapSize);
        }
    }
    public void swap(int[] nums,int i,int j){
        int tmp=nums[i];
        nums[i]=nums[j];
        nums[j]=tmp;
    }

归并排序

package org.example.lc;

public class Test03 {
    public static void main(String[] args) {
        //归并排序
        int[] nums=new int[]{9,8,7,6,5,4,3,2,1};
        int[] temp=new int[nums.length];
        mergeSort(nums,0,nums.length-1,temp);
        for(int i=0;i<nums.length;i++){
            System.out.print(nums[i]+" ");
        }
    }
    public static void mergeSort(int[] nums,int left,int right,int[] temp){
        if(left<right){
            int mid=(left+right)/2;
            mergeSort(nums,left,mid,temp);
            mergeSort(nums,mid+1,right,temp);
            merge(nums,left,mid,right,temp);
        }
    }
    public static void merge(int[] nums,int left,int mid,int right,int[] temp){

        int l=left,r=mid+1;
        int index=0;
        while(l<=mid&&r<=right){
            if(nums[l]<nums[r]){
                temp[index++]=nums[l++];
            }else{
                temp[index++]=nums[r++];
            }
        }
        while(l<=mid){
            temp[index++]=nums[l++];
        }
        while(r<=right){
            temp[index++]=nums[r++];
        }

        int idx=0;
        for(int i=left;i<=right;i++){
            nums[i]=temp[idx++];
        }

    }
}

桶排序

• 首先指定超参数 每一个桶的元素个数 ，确定需要的桶的个数bucketcount
• 对于最大最小值范围内的每一个数 唯一对应的桶为 (nums[i]-minv)/(maxv-minv+1)*bucketcount
• 将每一个元素通过插入排序的方式放入每一个桶
• 将所有的桶元素 通过有序数组合并

package org.example.lc;

import java.util.Arrays;

public class Test16 {
    public static void main(String[] args) {
        //桶排序
        int[] nums=new int[]{7,12,56,23,19,33,35,42,42,2,8,22,39,26,17};
        bucketSort(nums);
        for(int i=0;i<nums.length;i++){
            System.out.print(nums[i]+" ");
        }
    }
    public static void bucketSort(int[] nums){
        if(nums==null||nums.length==0){
            return;
        }
        int n=nums.length;
        //每一个桶的元素个数
        int bucketCount=n/4;//桶的个数
        int maxv=Integer.MIN_VALUE;int minv=Integer.MAX_VALUE;
        for(int i=0;i<n;i++){
            maxv=Math.max(maxv,nums[i]);
            minv=Math.min(minv,nums[i]);
        }
        //二维数组模拟每一个桶，以及每一个桶里面的元素
        int[][] buckets=new int[bucketCount][];

        for(int i=0;i<n;i++){
            int bucketIndex=(nums[i]-minv)/(maxv-minv+1)*bucketCount;
            buckets[bucketIndex]=insert(buckets[bucketIndex],nums[i]);
        }

        //将所有桶合并
        int index=0;
        for(int i=0;i<bucketCount;i++){
            if(buckets[i]!=null){
                for(int j=0;j<buckets[i].length;j++){
                    nums[index++]=buckets[i][j];
                }
            }
        }

    }
    public static int[] insert(int[] buckets,int val){
        //如果是一个空桶
        if(buckets==null||buckets.length==0){
            return new int[]{val};
        }
        int[] res= Arrays.copyOf(buckets,buckets.length+1);
        for(int i=buckets.length-1;i>=0;i--){
            if(res[i]>val){
                res[i+1]=res[i];
            }else{
                res[i+1]=val;
                break;
            }
        }
        return res;
    }
}