12.1 排序基础知识

比较选择排序、插入排序、冒泡排序、希尔排序、计数排序、归并排序、快速排序和堆排序优劣

	是否稳定	时间复杂度	空间复杂度	备注
选择排序	否	$N^2$	1
插入排序	是	$N$~$N^2$	1	与输入的排列情况有关
冒泡排序	是	$N^2$	1
希尔排序	否	小于$N^2$	1
计数排序	否	$N+k$	k
归并排序	是	$NlogN$	N
快速排序	否	$NlogN$	logN	运行效率概率保证
堆排序	否	$NlogN$	1

Q74：区间合并

题目（中等）：输入一个区间的集合，请将重叠的区间合并。每个区间用两个数字比较，分别表示区间的起始位置和结束位置。

示例 1：

输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6]
复制代码

示例 2：

输入：intervals = [[1,4],[4,5]]
输出：[[1,5]]
解释：区间 [1,4] 和 [4,5] 可被视为重叠区间
复制代码

解题思路

1. 按左边界排序
2. 右边界与后一区间左边界比较

public int[][]  merge(int[][] intervals){
    Arrays.sort(intervals,(i1,i2)->i1[0]-i2[0]);//按区间左边界排序

    List<int[]> merged = new LinkedList<>();
    int i = 0;
    while(i<intervals.length){
        int[] temp = new int[] {intervals[i][0],intervals[i][1]};//临时存放第i个区间
        int j = i + 1;
        while (j<intervals.length && intervals[j][0]<=temp[1]){
            temp[1] = Math.max(temp[1],intervals[j][1]);
            j++;
        }

        merged.add(temp);
        i=j;
    }

    int[][]result = new int[merged.size()][];
    return merged.toArray(result);
}
复制代码

12.2 计数排序

适用于数组长度N远大于整数范围大小k情况

Q75：数组相对排序

题目（简单）：输入两个数组arr1和arr2，其中arr2中的每一个数字都唯一，且都是arr1中的数字。请将数组arr1中的额数字按照数组arr2中的数字的相对顺序排序。如果数组arr1中的数字在数组arr2中没有出现，那么将这些数字按递增的顺序排在后面。假设数组中所有的数字都在0到1000范围内。

示例：

输入：arr1 = [2,3,1,3,2,4,6,7,9,2,19], arr2 = [2,1,4,3,9,6]
输出：[2,2,2,1,4,3,3,9,6,7,19]
复制代码

解题思路

1. 计数
2. 写入输出

public int[] relativeSortArray (int[] arr1,int[] arr2){
    int[] counts = new int[1001];
    //先计数
    for (int num : arr1) {
        counts[num-min]++;
    }
    //按arr2输出
    int i = 0;
    for (int num : arr2) {
        for(;counts[num-min]>0;i++){
            arr1[i] = num;
            counts[num-min]--;
        }
    }
    //剩下按顺序输出
    for (int num : arr1) {
        for(;counts[num-min]>0;i++){
            arr1[i] = num;
            counts[num-min]--;
        }
    }
    return arr1;
}
复制代码

12.3 快速排序

数组切分（partition），递归

Q76：数组中第k大的数字

题目（中等）：请从一个乱序数组中找出第k大的数字

示例 1:

输入: [3,2,1,5,6,4] 和 k = 2
输出: 5
复制代码

示例 2:

输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4
复制代码

public static int findKthLargest(int[] a,int k){
    int N = a.length;
    return findKthLargest(a,N-k,0,N-1);
}
private static int findKthLargest(int[] a,int k,int lo,int hi){
    if(lo==hi) return a[hi];
    int j = partition(a,lo,hi);
    if(k<j){return findKthLargest(a,k,lo,j-1);}
    if(k>j){return findKthLargest(a,k,j+1,a.length-1);}
    else return a[j];
}
private static int partition(int[] a,int lo,int hi){
    int i = lo;
    int j = hi+1;
    while(true) {
        while (less(a, ++i, lo)) if(i==hi)break;//左指针逼近
        while (less(a, lo, --j)) if(j==lo)break;//右指针逼近
        if (i>=j)break;
        exch(a,i,j);
    }
    exch(a,lo,j);
    return j;
}

private static boolean less(int[] a,int i,int j){
    return a[i] < a[j];
}
private static void exch(int[] a,int i,int j){
    int temp;
    temp = a[i];
    a[i] = a[j];
    a[j] = temp;
}
复制代码

12.4 并归排序

Q77：链表排序

题目（中等）：输入一个链表的头节点，请将该链表排序。

示例 1：

输入：head = [4,2,1,3]
输出：[1,2,3,4]
复制代码

示例 2：

输入：head = [-1,5,3,4,0]
输出：[-1,0,3,4,5]
复制代码

解题思路

1. 分，利用双指针确定第二子链表的头节点
2. 递归
3. 合，

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){//因为fast要走两步
        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 = head2;
            head2 = head2.next;//后移
        }else{
            cur.next = head1;
            head1 = head1.next;
        }
        cur = cur.next;
    }
    //接上没合并完的部分
    cur.next = head1 == null ? head2 : head1;
    return dummy.next;
}

public class ListNode{
    public int val;
    public ListNode next;

    public ListNode(int val){
        this.val = val;
    }

    public ListNode append(ListNode head,int val){
        ListNode newNode = new ListNode(val);
        if(head == null) return newNode;

        ListNode node = head;//保存head位置
        while (node.next!=null) node = node.next;
        node.next = newNode;
        return head;
    }
}
复制代码

Q78：合并排序链表

题目（困难）：输入k个排序的列表，请将他们合并成一个排序的链表。

示例 1：

输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
  1->4->5,
  1->3->4,
  2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6
复制代码

示例 2：

输入：lists = []
输出：[]
复制代码

示例 3：

输入：lists = [[]]
输出：[]
复制代码

利用最小堆实现

public ListNode mergeKLists(ListNode[] lists){
    ListNode dummy = new ListNode(0);
    ListNode cur = dummy;

    PriorityQueue<ListNode> minHeap = new PriorityQueue<>((v1,v2)->v1.val-v2.val);
    for (ListNode list : lists) {//先填充一轮
        if(list != null){
            minHeap.offer(list);
        }
    }
    while(!minHeap.isEmpty()){//当前最小节点
        ListNode least = minHeap.poll();
        cur.next = least;
        cur = cur.next;

        if(least.next != null){//如果还没并完，少了就补
            minHeap.offer(least.next);
        }
    }
    return dummy.next;
}
//链表
public class ListNode{
    public int val;
    ListNode next;

    public ListNode(int val) {
        this.val = val;
    }
}
复制代码

利用归并排序

public ListNode mergeKLists(ListNode[] lists){
    if(lists.length == 0){return null;}

    return mergeKLists(lists,0,lists.length-1);
}

private ListNode mergeKLists(ListNode[] lists, int lo, int hi){
    //递归初始项
    if(lo == hi){
        return lists[lo];
    }

    int mid = (lo + hi) / 2;
    //递归
    ListNode head1 = mergeKLists(lists,lo,mid);
    ListNode head2 = mergeKLists(lists,mid,hi);
    //合并
    return merge(head1,head2);
}
//即Q77.merge
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 = head2;
            head2 = head2.next;//后移
        }else{
            cur.next = head1;
            head1 = head1.next;
        }
        cur = cur.next;
    }
    //接上没合并完的部分
    cur.next = head1 == null ? head2 : head1;
    return dummy.next;
}
//链表
public class ListNode{
    public int val;
    ListNode next;

    public ListNode(int val) {
        this.val = val;
    }
}
复制代码

---

补充

结合《算法 v4》

选择排序

思想

依次找到第i号元素之后的最小元素，将两元素交换（交换过程会导致不稳定）

特点

• 运行时间和输入的初始状态没有关系
• 数据移动最少
• 时间复杂度 $N^2$，两层for循环

//选择排序
public static void selectionSort(Comparable[] a){
    int N = a.length;
    for (int i = 0; i < N; i++) {
        int min = i;
        //找出i位之后最小元素索引
        for (int j = i+1; j < N; j++) {
            if(less(a[j],a[min])) min = j;
        }
        exch(a,i,min);//在这一步i号元素和i之后最小元素交换会破坏相对顺序
    }
}
复制代码

插入排序

思想

把i号元素依次插入到已经有序的数组中

特点

• 运行时间和输入的初始状态有关（部分有序情况下更快，逆序数组最耗时）
• 时间复杂度 $N^2$，两层for循环

//插入排序
public static void insertionSort(Comparable[] a){
    int N = a.length;
    for (int i = 1; i < N; i++) {
        Comparable temp = a[i];//临时存放
        int j;
        for(j = i;j>0 && less(a[j],a[j-1]);j--)
            a[j-1] = a[j];
        a[j] = temp;
    }
}
复制代码

冒泡排序

思想

每次都把最大的元素往后面沉

特点

• 时间复杂度 $N^2$，两层for循环

//冒泡排序
public static void bubbleSort(Comparable[] a){
    int N = a.length;
    for (int i = 0; i < N; i++) {
        for ( int j = 1;j < N-i;j++){
            if(less(a[j],a[j-1])) exch(a,j,j+1);
        }
    }
}
复制代码

希尔排序

思想

让任意间隔为h的元素都是有序的

h逐渐减小，这里代码中，h序列采用$\frac{1}{2}(3^k-1)$序列

$\frac{1}{2}(3^k-1)=3*(\frac{1}{2}(3^{k-1}-1))+1$，亦即代码中的$h=3h+1$

特点

• 时间复杂度要小于 $N^2$，具体和h序列的选择有关系

//希尔排序
public static void shellSort(Comparable[] a){
    int N = a.length;
    int h = 1;
    //找到最接近数组大小的h值
    while(h<N/3) h = 3*h+1;//h序列元素互质,1,4,13,40,121...
    for(;h>=1;h/=3){
        for (int i = h; i < N; i++) {//
            Comparable temp = a[i];
            int j;
            for ( j = i; j >= h && less(a[j],a[j-h]); j-=h) {
                a[j-h] = a[j];
            }
            a[j] = temp;
        }
    }
}
复制代码

用到的less、exch函数实现

//比较
private static boolean less(Comparable v,Comparable w){
    return v.compareTo(w)<0;
}

//交换
private static void exch(Comparable[] a,int i,int j){
    Comparable temp; temp = a[i]; a[i] = a[j]; a[j] = temp;
}
复制代码

计数排序

思想

统计每个元素出现的次数，按顺序结合次数输出（显然，不稳定）

特点

• 时间复杂度 $N+k$，k为元素的跨度，空间复杂度为$k$
• 适合元素范围小且大量重复的数组

//计数排序
public static void countSort(int[] a){
    int min = Integer.MAX_VALUE;
    int max = Integer.MIN_VALUE;
    //确定最大最小
    for (int num : a) {
        min = Math.min(a,min);
        max = Math.max(a,max);
    }
    int[] counts = new int[max-min+1];
    for (int num : a) {
        counts[num-min]++;
    }
    int i = 0;
    for (int num : a) {
        for(;counts[num-min]>0;i++){
            a[i] = num;
            counts[num-min]--;
        }
    }
}
复制代码

归并排序

思想

递归，把两个有序的数组合并成为一个更大的有序数组

特点

• 时间复杂度 $NlogN$，空间复杂度 $N$

//自顶向下归并排序
private static Comparable [] temp;
public static void mergeSort(Comparable[] a){
    temp = new Comparable[a.length];
    mergeSort(a,0,a.length-1);
}

public static void mergeSort(Comparable[]a,int lo,int hi){
    if(hi<=lo) return;
    int mid = lo+(hi-lo)/2;
    mergeSort(a,lo,mid);//左
    mergeSort(a,mid+1,lo);//右
    merge(a,lo,mid,hi);
}

private static void merge(Comparable[] a,int lo,int mid,int hi){
    int i = lo,j = mid+1;
    for(int k =lo;k<hi;k++){
        temp[k] = a[k];
    }
    for(int l =lo;l<=hi;l++){
        if(i>mid) a[l] = temp[j++];//左边先并完
        else if(j>hi) a[l] = temp[i++];//右边先并完
        else if (less(temp[i],temp[j])) a[l]=temp[i];//左边小于右边
        else a[l] = temp[j];
    }
}
复制代码

快速排序

思想

将数组递归分切分为大于和小于切分元素两部分

特点

• 原地排序
• 时间复杂度 $NlogN$，空间复杂度 $lgN$
• 很脆弱，切分元素选的不好容易出现低性能

public static void quickSort(Comparable[] a){
    StdRandom.shuffle(a);
    quickSort(a,0,a.length-1);
}
private static void quickSort(Comparable[] a,int lo,int hi){
    if(hi<=lo)return;
    int j = partition(a,lo,hi);
    quickSort(a,lo,j-1);
    quickSort(a,j+1,hi);
}

//切分
private static int partition(Comparable[] a,int lo,int hi){
    int i = lo,j = hi+1;
    Comparable temp = a[lo];
    while(true){
        while(less(a[++i],temp))if(i==hi) break;
        while(less(temp,a[--j]))if(j==lo) break;
        if(i>=j)break;
        exch(a,i,j);
    }
    exch(a,lo,j);
    return j;
}
复制代码

堆排序

思想

利用最大堆按递减顺序取出所有元素的到排序结果

特点

• 能够同时最优利用时间和空间大方法
• 时间复杂度 $NlogN$

//堆排序
public static void heapSort(Comparable[] a){
    int N = a.length;
    //先利用下沉构造堆
    for(int k = N/2;k >= 1;k--) sink(a,k,N);
    //逐步将大值从后往前排列
    while(N > 1){
        exch(a,1,N--);
        sink(a,1,N);
    }
}
复制代码

//优先队列
private Key[] pq;
private int N = 0;
//构造函数
public priorityQueue(int N) {
    pq = (Key[])new Comparable[N+1];
}

//插入
public void insert(Key v){
    pq[++N] = v;
    swim(N);
}

//删除
public Key delete(){
    Key max = pq[1];
    exch(1,N--);
    pq[N+1] = null;//防止对象游离
    sink(1);
    return max;
}

//上浮
private void swim(int k){
    while(k>1 && less(k/2,k)){
        exch(k/2,k);
        k/=2;
    }
}

//下沉
private void sink(int k){
    while(2*k<N){
        int j = 2*k;
        if(less(j,j+1) && j<N)j++;
        if(less(j,k)) break;
        exch(j,k);
        k=j;
    }
}
复制代码