一、主要内容

1) 排序
2) 二分
3) 前缀和 / 差分
4) 位运算
5) 双指针算法
6) 离散化
7) 区间合并

1.1、排序

排序：快速排序、归并排序

（1）首先是模板：

1、快排模板
 void quick_sort(int q[], int l, int r)
 {
    if(l == r) return;
    int i = l-1, j = r+1, x = q[l + r >> 1];
    while(i < j)
    {
        do i++; while(q[i] < x);
        do j--; while(q[j] > x);
        if(i < j) swap(q[i], q[j]);
    }
    quick_sort(q, l, j);
    quick_sort(q, j+1, r);
 }


2、归并模板
 int tmp[N];
 void merge_sort(int q[], int l, int r)
 {
    if(l == r) return;
    int mid = l + r >> 1;
    merge_sort(q, l, mid), merge_sort(q, mid+1, r);
    int i = l, j = mid+1, k = 0;
    while(i <= mid && j <= r)
    {
        if(q[i] <= q[j]) tmp[k++] = q[i++];
        else tmp[k++] = q[j++];
    }
    while(i <= mid) tmp[k++] = q[i++];
    while(j <= r) tmp[k++] = q[j++];

    for(int i=l,j=0; i<=r; i++) q[i] = tmp[j];
 }

（2）练习题：
LeetCode 21： 合并两个有序链表
LeetCode 148： 排序链表
LeetCode 23： 合并k个有序链表
LeetCode 426. 将二叉搜索树转化为排序的双向链表
LeetCode 215. 数组中的第K个最大元素