算法基础

  • 注意’输入’的时间问题，在C++中scanf()要比cin快，在Java中BufferRead要比Scanner快。
  • 为什么需要模板
    对于一些涉及到边界的问题，如果自己想会忽略很多情况，短时间内很难想全面，而合适的模板是经过千锤百炼，跑过各种各样的模型，适用于所想到的所有情况，所以要记忆必要的模板。

快速排序

  • 时间复杂度：O(nlogn)
    快速排序
  • 模板
1
2
3
4
5
6
7
8
9
10
11
12
13
void quickSort(int array[],int l,int r){
    if(l >= r)
        return;
    int x  = array[l];
    int i = l - 1, j = r + 1;
    while (i < j){
        do i++; while (array[i] < x);
        do j--; while (array[j] > x);
        if(i < j) swap(array[i],array[j]);
    }
    quickSort(array,l,j);
    quickSort(array,j+1,r);
}
  • 这是一个从小到大的快排模板，想要从大到小排列，while (array[i] < x);与while (array[i] > x);交换位置。
  • 为了照顾没有do while语言的朋友们，我们用while替代
1
2
3
4
5
6
7
8
9
10
11
12
13
void quickSort(int array[],int l,int r){
    if(l >= r)
        return;
    int x  = array[l];
    int i = l - 1, j = r + 1;
    while (i < j){
         while (array[++i] < x);
         while (array[--j] > x);
        if(i < j) swap(array[i],array[j]);
    }
    quickSort(array,l,j);
    quickSort(array,j+1,r);
}
  • 应该注意while (array[++i] < x);不能写成while (array[i++] < x);

注意：在这个模板中，给x赋值时不能x = array[r],否则会出现死循环，如[2,1]模型快排

快速选择算法 ？？？

  • 时间复杂度O(n)
  • 本质：在快排的基础上改进算法，形成了快速选择算法。判断k在sl的左右两侧，只对一侧进行快排。
  • 模板
1
2
3
4
5
6
7
8
9
10
11
12
13
14
int quickSearch(int *array,int l,int r,int k){
    if(l >= r)
        return array[l];
    int x = array[l], i = l - 1, j = r + 1;
    while (i < j){
        while (array[++i] < x);
        while (array[--j] > x);
        if(i < j)
            swap(array[i],array[j]);
    }
    int sl = j - l + 1;
    if(k <= sl) return quickSearch(array,l,j,k);
    return quickSearch(array,j+1,r, k - sl);
}

归并排序

  • 步骤
  1. 确定分界点mid：mid = (l + r) / 2
  2. 递归排序Left，Right
  3. 合并
    归并排序
  • 始终保持O(logn)的时间复杂度，但会牺牲额外数组空间。
  • 模板
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void merge_sort(int *q,int l,int r){
    if(l >= r)
        return;
    int mid = (l+r) / 2;
    merge_sort(q,l,mid);
    merge_sort(q,mid+1,r);
    int k = 0, i = l, j = mid + 1;// i j分别为两个数组的指针，双指针
    while (i <= mid && j <= r){
        if(q[i] < q[j]) tmp[k++] = q[i++];
        else tmp[k++] = q[j++];
    }
    //当一方数组的指针到尾，将另一个数组内的数全部移入tmp临时数组
    while (i <= mid) tmp[k++] = q[i++];
    while (j <= r) tmp[k++] = q[j++];

    //将tmp临时数组的内容移回q数组
    for(i = l,j = 0;i <= r;++i, ++j)q[i] = tmp[j];
}

注明：

数组在使用‘&’运算符的tips

  • 数组名的行为：在C语言中，数组名本身通常会被解释为指向数组第一个元素的指针。因此，直接使用数组名就已经是一个指针，它指向数组的第一个元素。即array等价于&array[0]
1
2
int array[10];
int *ptr = array;  // 等价于 int *ptr = &array[0];
  • 当取数组中某个元素的地址时，使用&的方式与普通变量相同，即&array[3]
1
2
int array[10];
int *ptr = &array[5];  // ptr存储array中第6个元素的地址
  • 如果对整个数组使用&运算符（例如&array），它的结果是一个指向数组的指针，类型是int (*)[10]（假设数组有10个元素）。这个指针指向整个数组，而不是数组的第一个元素。
1
2
int array[10];
int (*ptr)[10] = &array;  // ptr存储整个array数组的地址

数组

  • 数组的本质就是同一种类型元素的集合
  • 当定义一个函数参数为 int q[] 时，编译器实际上将其视为int，即一个指向整数类型的指针。这意味着可以传递一个数组的首地址给这个参数，而在函数内部你可以像访问数组一样访问这个指针。即在函数参数定义中void func(int q[]);与void func(int *q);是等价的。q[] 可以被视为一种语法糖，它在编译时会被转换为等效的指针运算。

tips

a++ & ++a

b = a++; 先计算表达式的值，即先把a赋值给了b；然后a再自加1。

1
2
3
4
5
6
7
int main(){
    int a = 1;
    int b;
    b = a++;
    cout << "b=" << b << endl;
    cout << "a=" << a << endl;
}

结果：a = 2,b = 1
b = ++a; 先a自加1后；然后把a自加后得到的赋值给b。

1
2
3
4
5
6
7
int main(){
    int a = 1;
    int b;
    b = ++a;
    cout << "b=" << b << endl;
    cout << "a=" << a << endl;
}

结果：a = 2,b = 2

  • while循环条件中i++与++i的区别
    i++：先判断–>再计算i=i+1–>最后进入循环体
    ++i：先计算i=i+1–>再判断–>最后进入循环体