5.5

快速排序模板类型

    主要思想：分治；

1. 对于这种边界容易出错的，直接背过模板就好

2. 这里是需要先找出x分界点对其进行比较，然后比较，最后递归，

3. void quick_sort(int q[], int l, int r) {    if (l >= r)//如果左边大于有右边那么不符合条件，退出        return;    int x = q[l], i = l - 1, j = r + 1;//取数组的边界区域    while (i < j) {        do            i++;        while (q[i] < x);        do            j--;        while (q[j] > x);        //两个指针都在走，当发现还是存在i<j的情况就交换，        if (i < j) {            swap(q[i], q[j]);        }    }    quick_sort(q, l, j);//分而治之    quick_sort(q, j + 1, r); }

    排序的稳定：原来两个数的值是相同的，如果排完序后位置不发生变换就是叫做问稳定，快排是不稳定的，除非将序列里面的数都是不同的

归并排序

主要思想

1. 归并需要先进行递归，最后再合

2. 分界点的位置 x左右两边的平均值

3. 三个指针，一个临时数组。

4. 通过分开的两个指针比较大小之后用一个临时数组的指针进行存储

5. 最后再将原来的数组给覆盖，最后这边思想需要多看看

6. 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 k = 0, i = l, j = mid + 1;    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 (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j]; } //转载至y总的算法模板：https://www.acwing.com/blog/content/277/

二分模板

1. 主要思想

• 如果想要查找的数小于中间边界就将mid赋值给左边界；

• 反之就赋值给右边界；

• 其实就是边界的问题，容易出错，两种模板

  • 找最大值中的最小:

  •  int main() {     int l;     int r;     while(l < r)     {         int mid = (l + r)/ 2;         if(check())//check函数就是需要判断是查找的数是跟左边比还是跟右边比，根据题目而定         {             r = mid;  // 这里是 r = mid, 说明[l,mid]是合法范围         }         else         {             l = mid + 1;   //  [l,mid]这个范围都不是合法范围，所以下一次查找直接从 l = mid + 1开始了         }         //最后的l,r是答案 因为 l == r ，最终就是答案。     }           } 

  • 找最小值中的最大:

  •  int main() {     int l;     int r;     while(l < r)     {         int mid = (l + r + 1)/ 2;  // 这里要 l + r +1 要不然会死循环         if(check())         {             l = mid;         // mid这个位置 满足条件之后 查找 [mid , right]的位置， 所以l移到mid的位置         }         else         {             r = mid - 1;     // [mid,r] 不满足条件， 所以要移到满足条件的一方， r = mid - 1          }     }      //最后的l,r是答案 因为 l == r  

} ```