第12章 排序

排序的基础知识

大根堆模板

/**
 * 调整为大顶堆
 * @param arr   待调整的数组
 * @param parent   当前父节点的下标
 * @param length   需要对多少个元素进行调整
 */
private static void adjustHeap(int[] arr, int parent, int length){
    //临时保存父节点
    int temp = arr[parent];
    //左子节点的下标
    int child = 2 * parent + 1;
    //如果子节点的下标大于等于当前需要比较的元素个数，则结束循环
    while(child < length){
        //判断左子节点和右子节点的大小,若右边大，则把child定位到右边
        if(child + 1 < length && arr[child] < arr[child + 1]){
            child ++;
        }
        //若child大于父节点，则交换位置，否则退出循环
        if(arr[child] > temp){
            //父子节点交换位置
            arr[parent] = arr[child];
            //因为交换位置之后，不能保证当前的子节点是它子树的最大值，所以需要继续向下比较，
            //把当前子节点设置为下次循环的父节点，同时，找到它的左子节点，继续下次循环
            parent = child;
            child = 2 * parent + 1;
        }else{
            //如果当前子节点小于等于父节点，则说明此时的父节点已经是最大值了，
            //因此无需继续循环
            break;
        }
    }
    //把当前节点值替换为最开始暂存的父节点值
    arr[parent] = temp;
}

public static void main(String[] args) {
    int[] arr = {4,1,9,3,7,8,5,6,2};
    //构建一个大顶堆，从最下面的非叶子节点开始向上遍历
    for (int i = arr.length/2 - 1 ; i >= 0; i--) {
        adjustHeap(arr,i,arr.length);
    }
    System.out.println(Arrays.toString(arr));
}    
//打印结果：  [9, 7, 8, 6, 1, 4, 5, 3, 2]。 和我们分析的结果一模一样

堆排序模板

归并排序模板

y总模板（可以将dst数组作为class的成员变量）：

class Solution {
    public int findKthLargest(int[] nums, int k) {
        int n=nums.length;
        int[] dst = new int[nums.length];
        mergeSort(nums, dst, 0, nums.length-1);
        //Arrays.sort(nums);
        for(int num:nums)
        System.out.println(num);
        return nums[n-k];
    }

    private void mergeSort(int[] nums,int[] dst,int left,int right){
        if(left >= right){
            return;
        }
        int mid = left+right>>1;
        mergeSort(nums, dst, left, mid);
        mergeSort(nums, dst, mid+1, right);
        int k=0, i=left, j=mid+1;
        while(i<=mid && j<=right){
            if(nums[i]<=nums[j]){
                dst[k++]=nums[i++];
            }else{
                dst[k++]=nums[j++];
            }
        }
        while(i<=mid) dst[k++]=nums[i++];
        while(j<=right) dst[k++]=nums[j++];
        for(i=left,j=0;i<=right;i++,j++){
            nums[i] = dst[j];
        }
    }
}

书上的模板：

class Solution {
    public int findKthLargest(int[] nums, int k) {
        int n=nums.length;
        int[] dst = new int[nums.length];
        dst = Arrays.copyOf(nums, nums.length);
        mergeSort(nums, dst, 0, nums.length-1);
        //Arrays.sort(nums);
        for(int num:dst)
            System.out.println(num);
        return nums[n-k];
    }

    private void mergeSort(int[] nums,int[] dst,int left,int right){
        if(left >= right){
            return;
        }
        int mid = left+right>>1;
        //注意这里交换了dst和nums的位置，相当于在最后交换了；否则dst相当于把原数组复制了一遍，还需要在后面进行交换。
        mergeSort(dst, nums, left, mid);
        mergeSort(dst, nums, mid+1, right);

        int i=left, j=mid+1, k=left;
        while(i<=mid || j<=right){
            if(j==right+1 ||(i<=mid && nums[i]<nums[j])){
                dst[k++] = nums[i++];
            }else{
                dst[k++] = nums[j++];
            }
        }
    }
}

剑指offerⅡ74：合并区间

计数排序

剑指offerⅡ75：数组相对排序

快速排序

剑指offerⅡ76：数组中第K大的数字

给定整数数组 nums 和整数 k，请返回数组中第 **k**个最大的元素。

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

class Solution {
    public int findKthLargest(int[] nums, int k) {
        quick_select(nums,0,nums.length-1,k);
        return nums[nums.length-k];
    }

    private void quick_select(int[] nums, int left, int right, int k){
        if(left>=right){
            return;
        }
        int i=left-1, j=right+1, x=left;
        while(i<j){
            while(nums[++i]<nums[x]);
            while(nums[--j]>nums[x]);
            if(i<j){
                int temp = nums[i];
                nums[i] = nums[j];
                nums[j] = temp;
            }
        }
        if(nums.length-k<=j)
            quick_select(nums,left,j,k);
        if(nums.length-k>=j+1)
            quick_select(nums,j+1,right,k);
    }
}

归并排序

剑指offerⅡ77：链表排序

给定链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。

class Solution {
    public ListNode sortList(ListNode head) {
        if(head==null || head.next==null){
            return head;
        }
        ListNode head1 = head;
        ListNode head2 = split(head);

        head1 = sortList(head1);
        head2 = sortList(head2);
        return merge(head1,head2);
    }

    private ListNode split(ListNode head){
        ListNode slow = head;
        ListNode fast = head.next;
        while(fast!=null && fast.next!=null){
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode second = slow.next;
        slow.next = null;
        return second;
    }

    private ListNode merge(ListNode head1, ListNode head2){
        ListNode dummy = new ListNode(0);
        ListNode cur = dummy;
        while(head1!=null && head2!=null){
            if(head1.val < head2.val){
                cur.next = head1;
                head1 = head1.next;
            }else{
                cur.next = head2;
                head2 = head2.next;
            }
            cur = cur.next;
        }
        cur.next = head1==null ? head2 : head1;
        return dummy.next;
    }
}

剑指offerⅡ78：合并排序链表

给定一个链表数组，每个链表都已经按升序排列。

请将所有链表合并到一个升序链表中，返回合并后的链表。

利用堆选取值的最小点：

最low的办法：把每个节点放入小根堆中。或者放入list中，调用collections的自定义排序算法。

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        ListNode dummy = new ListNode(0);
        ListNode cur = dummy;
        PriorityQueue<ListNode> minHeap = new PriorityQueue<ListNode>((a,b)->(a.val-b.val));
        for(ListNode node:lists){
            while(node!=null){
                minHeap.offer(node);
                node=node.next;
            }
        }
        while(!minHeap.isEmpty()){
            cur.next = minHeap.poll();
            cur = cur.next;
        }
        cur.next=null;//这里尾节点最后一定为null，否则会出错
        return dummy.next;
    }
}

不那么low的办法：把一个个链表放入小根堆中，不断弹出放入。比上个方法好在节省大量空间。

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        ListNode dummy = new ListNode(0);
        ListNode cur = dummy;
        PriorityQueue<ListNode> minHeap = new PriorityQueue<ListNode>((a,b)->(a.val-b.val));
        for(ListNode list:lists){
            if(list!=null){
                minHeap.offer(list);
            }
        }
        while(!minHeap.isEmpty()){
            cur.next = minHeap.poll();
            cur = cur.next;
            if(cur.next!=null){
                minHeap.offer(cur.next);
            }
        }
        //这里不用加cur.next，因为小根堆里面存的是一个个list，后面的内容本身都是一个子链表，尾部都有null节点
        return dummy.next;
    }
}

按照归并排序的思路合并链表：

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if(lists.length == 0){
            return null;
        }
        return mergeLists(lists,0,lists.length-1);
    }

    private ListNode mergeLists(ListNode[] lists, int left, int right){
        if(left>=right){
            return lists[left];
        }
        int mid = left+right>>1;
        ListNode head1 = mergeLists(lists,left,mid);
        ListNode head2 = mergeLists(lists,mid+1,right);
        return merge(head1,head2);
    }

    private ListNode merge(ListNode head1, ListNode head2){
        //if(head1==head2)return head1;没有必要加这句，因为传进来的head1和head2必然是不同的
        ListNode dummy = new ListNode(0);
        ListNode cur = dummy;
        while(head1!=null && head2!=null){
            if(head1.val<head2.val){
                cur.next = head1;
                head1=head1.next;
            }else{
                cur.next = head2;
                head2=head2.next;
            }
            cur = cur.next;
        }
        cur.next = (head1==null) ? head2 : head1;
        return dummy.next;
    }
}