归并+快排+随机数+随机数快排->two points

算法思想：
略，应该很简单了

int partition(int a[], int left, int right) {
    int temp = a[left]; 
    while (left < right) {
        while (left < right && a[right] > temp) right--;
        a[left] = a[right];
        while (left < right && a[left] <= temp) left++;
        a[right] = a[left];
    }
    a[left] = temp;
    return left;
}

void quicksort(int a[], int left, int right) {
    if (left < right) {
        int pos = partition(a, left, right);
        quicksort(a, left, pos - 1);
        quicksort(a, pos + 1, right);
    }
}

优化，随机数算法写快排
learn && wrong:
1、包括库函数<time.h>和<stdlib.h>
2、srand(unsigned)函数和time()函数 + rand()函数
3、rank（）函数只能怪【0，rand_max】范围内的整数(rand_max是stdlib.h中一个常数，不同系统有所不同
如果想要给定输出范围的随机数函数，则使用rand() % (b - a + 1),范围是[0,b - a]
再加上a，就是【a,b】
4、生成更大范围的随机数：先用rand()生成一个[0,rand_manx()]范围内的随机数，然后用这个随机数除以rand_max，这样就会得到一个[0,1]范围内的浮点数。
接下来用这个浮点数乘以范围（b - a + 1）即可，再加上aj即可

本质：是生成一个比例，乘以范围，再加上起点

#include <stdlib.h>
#include <time.h>
#include <cstdio>
using namespace std;
int main() {
    srand((unsigned)time(NULL));
    for (int i = 0;i < 10;++i) { //10000,60000
        printf("%d",(int)(round(1.0 * rand() / RAND_MAX) * 50000 + 10000))
    }
  return 0;
}

5、随机数快排，
1、现在[left,right]内生成一个随机数p,然后以A[P]作为主元来划分。
2、将a[p]与a[left]交换，然后按原先partition函数的写法即可。（其实就是加两句话）

int randpartition(int a[], int left, int right) {
    int p = (round(1.0 * rand() / max_rand) * (right - left ) + left;
        swap(a[left],a[p]);
        int temp = a[left]; 
    while (left < right) {
        while (left < right && a[right] > temp) right--;
        a[left] = a[right];
        while (left < right && a[left] <= temp) left++;
        a[right] = a[left];
    }
    a[left] = temp;
    return left;
}