1. 快排算法

输出的前k个最小数，均有序，时间复杂度为O(nlogn)，空间为O(logn)

package demo1;

import java.util.Arrays;

public class demo2 {
    
    public static void main(String[] args) {
    
        //快排算法
        int[] data=new int[]{
    1,4,5,3,2,6,7,9,8};
        int k=5;
        System.out.println(Arrays.toString(data));
        fastsort(data,0,data.length-1,k);
        System.out.println(Arrays.toString(data));
    }
    public static void fastsort(int[] data,int first,int last,int k){
    
        //特殊情况
        if(first>last) return ;
        //一般情况
        //1）找到一个随机数，以此为基准进行交换
        int left=first;
        int right=last;
        int temp=data[first];  //挑选出来的基准
        while(left<right){
    

            //1)找到需要交换对象(如果左边为基准，那么从右边开始寻找)
            while(left<right && data[right]>temp) right--;
            while(left<right && data[left]<=temp) left++;
            //2)找到之后就进行交换
            if(left<right){
    
                int temp1=data[left];
                data[left]=data[right];
                data[right]=temp1;
            }
        }
        //把基准的位置也换一下
        data[first]=data[left];
        data[left]=temp;
        //继续递归下去(以left为界限）
        if(left+1<k){
    
            fastsort(data,left+2,last, k-left-1);
        }else if(left==k){
    
            return;
        }else{
    
            fastsort(data,first,left,k);
        }

    }
}

2. 堆排序

1） 小顶堆排序算法（通过一个数组，大顶堆，子节点大于等于孩子节点的完全二叉树）
2）调用实现了大顶堆的集合PriorityQueue,默认为小顶堆，可重写Comparator中的类compare，实现大顶堆。
3）时间复杂度为O(nlogn),空间复杂度O(1)

package demo1;

import java.util.*;

public class demo4 {
    
    public static void main(String[] args) {
    
        List<Integer> list=new ArrayList<>(Arrays.asList(2,3,1,5,7,6,9,8,0));
        int k=8;
        PriorityQueue<Integer>  queue=new PriorityQueue<>(new Comparator<Integer>(){
    
            @Override
            public int compare(Integer a,Integer b){
    
                return a-b;
            }
        });

        for(Integer i:list) queue.add(i);
        System.out.println(queue);
        for(int i=0;i<k;i++) System.out.print(queue.poll()+" ");

    }
}

3. 快排改进算法

1. 快排思想算法（输出的前k个最小数，无序），时间复杂度为O(n),空间为常量空间
2. 借鉴了快排思想，在递归操作那里多了个选择

package demo1;

import java.util.Arrays;

public class demo3 {
    
    public static void main(String[] args) {
    
        //重写:快排算法
        int[] data=new int[]{
    2,6,7,9,8,1,4,5,3};
        //int[] data=new int[]{3,2,4,1,5,8,7};
        int k=4;
        fastsort(data,0,data.length-1,k);
        System.out.println("data="+ Arrays.toString(data));
        int[] data1=Arrays.copyOfRange(data,0,k);
        System.out.println("result="+ Arrays.toString(data1));

    }
    public static void fastsort(int[]data,int begin,int end,int k){
    
        //特殊情况
        if(begin>end) return;
        //一般情况
        int left=begin;
        int right=end;
        int temp=begin;
        while(left<right){
    
            //寻找到可以交换的(参考值为左边的，寻找从右边开始）
            while(left<right && data[right]>data[temp]) right--;
            while(left<right && data[left]<=data[temp]) left++;
            //寻找到之后进行交换
            if(left<right){
    
                int tem1=data[right];
                data[right]=data[left];
                data[left]=tem1;
            }
        }
        //然后参考值放到该放的位置上
        int tem2=data[left];
        data[left]=data[begin];
        data[begin]=tem2;
        System.out.println("data="+ Arrays.toString(data));
        
        //进行下面的递归操作(核心代码，找到中间位置就是参考值
            if(left+1<k){
    
                fastsort(data,left+1,end,k);
            }else if(left==k || left+1==k ){
    
                return;
            }else{
    
                fastsort(data,begin,left,k);
            }
    }
}

易错点：
1）在方法中，首先应该对begin>end情况进行讨论
2）在找到合适交换值时，如果参考值为第一个，那么就从右边开始找，然后找左边
3）注意一下递归选择的情况。