FindK、快排、堆排序

1、快排解法

public class QuickSort {

    static int partition(int[] a,int left,int right){
        if (left >= right || a == null || a.length <= 1) {
            return;
        }
        int pivot = a[left];
        while (left < right){
            while(a[right] < pivot && left < right){
                right--;
            }

            if(left < right){
                a[left] = a[right];
                left++;
            }

            while(a[left] > pivot && left < right){
                left++;
            }

            if(left < right){
                a[right] = a[left];
                right--;
            }
        }
        a[left] = pivot;
        return left;
    }

    static void quickSort(int[] a,int left,int right){
        if (left >= right) {
            return;
        }
        int pivot = partition(a,left,right);
        quickSort(a,left,pivot-1);
        quickSort(a,pivot+1,right);
    }

    static void quickSortTest(){
        int array[] = {20,50,20,40,70,10,80,30,60};
        System.out.println("排序之前：");
        for(int element : array){
            System.out.print(element+" ");
        }
        System.out.println();
        quickSort(array,0, array.length-1);
        System.out.println("\n排序之后：");
        for(int element : array){
            System.out.print(element+" ");
        }
        System.out.println();
    }


    static int findK(int[] a,int left,int right,int k){
        int pivot = partition(a,left,right);
        if(pivot == k-1){
           return a[pivot];
        }else if(pivot > k-1){
            return findK(a,left,pivot-1,k);
        }else{
            return findK(a,pivot+1,right,k);
        }
    }

    static void findKTest(){
        int array[] = {20,50,20,40,70,10,80,30,60};
        System.out.println(findK(array,0,array.length-1,8));
    }


    public static void main(String[] args){
//        quickSortTest();
        findKTest();
    }

2、堆排解法

public class HeapSort {

    static void swap(int[] a,int i,int j){
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

    static void maxHeapify(int[] a ,int index,int len){
        int left = (index << 1) + 1; // 左子节点索引
        int right = left + 1;
        int cMax = left;

        if(left > len) return;       // 左子节点索引超出计算范围，直接返回。
        if(right < len && a[left] < a[right]){
            cMax = right;
        }

        if(a[cMax] > a[index]){
            swap(a,index,cMax);
            maxHeapify(a,cMax,len);
        }
    }


    static void heapSort(int[] a){
        int len = a.length -1;
        if(a == null || a.length < 1){
            return;
        }

        int beginIndex = (len - 1) >> 1;

        for (int i = beginIndex ; i >=0 ; i--) {
            maxHeapify(a,i,len);
        }

        while(len >=0){
            swap(a,0,len--);
            maxHeapify(a,0,len);
        }
    }


    static void findK(int[] a,int k){
        int len = a.length -1;
        if(a == null || a.length < 1 || k > len){
            return;
        }

        for (int i = (len/2 -1); i >=0 ; i--) {
            maxHeapify(a,i,len);
        }

        while((k--) > 1){
            swap(a,0,len--);
            maxHeapify(a,0,len);
        }
    }


    static void heapSortTest(){
        int array[] = {20,50,20,40,70,10,80,30,60};
        System.out.println("排序之前：");
        for(int element : array){
            System.out.print(element+" ");
        }
        System.out.println();
        heapSort(array);
        System.out.println("\n排序之后：");
        for(int element : array){
            System.out.print(element+" ");
        }
        System.out.println();
    }

    static void findKTest(){
        int array[] = {20,50,20,40,70,10,80,30,60};
        int k = 3 ;
        findK(array,k);
        System.out.println("K ="+k+"   K NUM ="+array[0]);
    }


    public static void main(String[] args){

        heapSortTest();

        findKTest();

    }
}