算法笔记 双指针

本文将介绍双指针法（又叫 two pointers）这一重要的算法思想。

一、什么是双指针

递增序列元素和等于目标数

给定一个递增的正整数序列和一个正整数 M ，求序列中的两个不同位置的数 a 和 b ，使它们的和恰好为 M，输出所有满足条件的方案。

例如：序列{1, 2, 3, 4, 5, 6}，正整数 M = 8，则存在 2, 6 和 3, 5 两种方案。

(1) 二重循环法

本体的一个直观想法是，使用二重循环枚举序列中的整数 a 和 b ，判断它们的和是否为 M，如果是，输出方案；如果不是，则继续枚举。

解题代码：

1
2
3
4
5
6
7
8
void fun(int a[], int n, int M){
	int i, j;
	for (i = 0; i < n; i++){
		for (j = i + 1; j < n; j++){
			if (a[i] + a[j] == M)    printf("%d %d\n", a[i], a[j]);
		}
	}
}

此算法的复杂度为 o(n2) ，在数组规模比较大时将无法承受。在解题过程中，进行了很多无效枚举，效率低下。

(2) 双指针法

解题思路：

  • 令 i = 0 ， j = n - 1 ，双指针分别指向序列的头尾。约定 i, j 都只能向序列中间移动。

  • 当 i < j 时，

    • 若 a[i] + a[j] < M ，令左指针自增；

    • 若 a[i] + a[j] > M ，令右指针自减；

    • 若 a[i] + a[j] == M ，显然，a[i] + a[j - 1] 必定小于 M ，而 a[i + 1] + a[j] 必定大于 M。因此，令 i++, j-- 。

解题代码：

1
2
3
4
5
6
7
8
9
10
11
12
void fun(int a[], int n, int M){
	int i, j;
    for (i = 0, j = n - 1; i < j; ){
        if (a[i] + a[j] > M)    j--;
        else if (a[i] + a[j] < M)    i++;
        else{
            printf("%d %d", i, j);
            i++;
            j--;
        }
    }
}

该算法的时间复杂度为 o(n) ，比暴力的二重循环法优秀很多。

序列合并问题

假设由两个递增序列 A 和 B ，要求把它们合并为一个递增序列 C 。

解题思路：

  • 令 i = 0 ， j = 0 ，分别指向两个序列的第一个元素。
  • 当 i, j 都没有到达序列的末端时，
    • 若 A[i] < B [i] ，将 A[i] 加入 C ， i 自增。
    • 若 A[i] > B [i] ，将 B[j] 加入 C ， j 自增。
    • 若 A[i] == B [i] ，任选一个加入 C ，对应下标自增。
  • 将剩余元素的序列中所有剩余元素依次放入 C 中。

解题代码：

1
2
3
4
5
6
7
8
9
10
11
int Merge(int A[], int B[], int C[], int n, int m){
	int i, j, k;
	i = j = k = 0;
	while (i < n && j < n){
		if (A[i] <= B[j])    C[k++] = A[i++];
		else    C[k++] = A[j++];
	}
	while (j < n)    C[k++] = A[j++];
	while (i < n)    C[k++] = A[i++];
	return k;  //返回C的长度
}

​

二、归并排序

递归地将序列不断向下拆分，然后将拆成的元素两两合并、四四合并 ······ ，直至合并成一整个数组。

递归排序的时间复杂度为 o(nlogn) ，稳定，是一种优秀的排序算法。

1.递归实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//全局辅助数组  也可以用其它方式解决，比如每次在函数中新建、数组做函数参数
int *B = (int*)malloc(sizeof(int) * n);  
void Merge(int A[], int low, int mid, int high){
	for (i = low; i <= high; i++)    B[i] = A[i];
	for (i = low, j = mid + 1, k = low; i <= mid && j <= high;k++){
		if (B[i] <= B[j])    A[k] = B[i++];
		else    A[k] = B[j++];
	}
	while (i <= mid)    A[k++] = B[i++];
	while (j <= high)    A[k++] = B[j++];
}
void MergeSort(int A[], int low, int high){
	if (low < high){  //low < high 说明未拆分到底
		mid = (low + high) / 2;
		MergeSort(A,low,mid);
		MergeSore(A,mid + 1,high);
		Merge(A,low,mid,high);
	}
}

2.非递归实现

每次分组时组内元素的个数上限都是 2 的幂次。

因此可以想到这样一个思路：令步长 step 的初值为 2 ，然后将数组中每 step 个元素作为一组，将其内部进行排序；然后再令 step 乘以 2 ，重复上面的操作，直至 step / 2 操作元素个数 n 。

下面的代码有修改，与书上不同，个人觉得更好理解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void MergeSort(int A[], int n){
	int i;
	int step;  //排序个数
	for (step = 2; step <= n; step *= 2){  //每轮循环使排序个数翻倍
		for (i = 0; i < n; i += step){
			Merge(A, i, i + step / 2 - 1, min(i + step - 1, n - 1));
		}
	}
	/*
	需要一趟额外的归并排序
	step翻倍后大于n时，数组整体还是不有序
	仅是在 0 ~ step/2-1 和 step/2 ~ n-1 两个区间内局部有序，所以需要再进行一轮排序
	*/
    Merge(A, 0, step / 2 - 1, n - 1);
}

​

三、快速排序

递归地对序列进行“左小右大”的划分，每一轮划分确定一个元素的位置，直至每个部分都被划分得只有一个元素为止。

递归排序的时间复杂度为 o(nlogn) ，不稳定，是一般而言性能最好的排序算法。

1.划分

解题思路：

  • 先将最左边的元素用 temp 存储

  • 令 low, high 分别指向序列的头尾

    • 若 high 指向的元素大于等于 temp ，就将 high 不断自减
    • 令 A[low] = A[high]
    • 若 low 指向的元素小于等于 temp ，就将 low 不断自增
    • 令 A[high] = A[low]

    之所以是大于等于，是为了防止死循环。

    在这里“放跑”的等于数字，会在之后的递归划分中放到该在的位置

  • 当 low 与 high 相遇时，说明划分结束，在相遇位置填入此前保存在 temp 中的值，返回相遇位置

解题代码：

1
2
3
4
5
6
7
8
9
10
11
int Partition(int A[],int low, int high){
	temp = A[low];
	while (low < high){
		while (A[high] >= temp && low < high)    high--;
		A[low] = A[high];
		while (A[low] <= temp && low < high)    low++;
		A[high] = A[low];
	}
	A[low] = temp;
	return low;
}

2.快速排序

解题思路：

  • 对序列进行划分
  • 对划分出来的左子序列进行划分，对划分出来的右子序列进行划分
  • 递归向下划分，直至 low < high ，即子序列只有一个元素

解题代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int Partition(int A[],int low, int high){
	temp = A[low];
	while (low < high){
		while (A[high] >= temp && low < high)    high--;
		A[low] = A[high];
		while (A[low] <= temp && low < high)    low++;
		A[high] = A[low];
	}
	A[low] = temp;
	return low;
}
void QuickSort(int A[],int low, int high){
	if (low < high){
		int flag = Partition(A, low, high);
		QuickSort(A,low, flag - 1);
		QuickSort(A,flag + 1, high);
	}
}

3.算法优化

(1) 优化思路

快速排序算法当序列中元素的排列比较随机时效率最高，但是当序列中元素接近有序时会达到最坏时间复杂度 o(n2) 。

最好的情况，每次划分区间为平均的两半，划分 logn 次即可；

最坏的情况，每次只能将区间分为 1 和 n - 1，需要划分 n 次。

有一个解决这一题的办法：随机选择“枢轴”，也就是不再每次都选择最左边的元素作为“枢轴”，而是从序列中随机选择一个作为枢轴。

这样虽然算法的最坏时间复杂度仍然是 o(n2) ，但对任意输入数据的期望时间复杂度都能达到 o(nlogn) ，也就是说，不存在一组特定的数据能使这个算法出现最坏情况。

具体证明可以参考《算法导论》

(2) 随机数

获得随机数：

1
2
3
4
5
6
7
8
9
//必须的头文件
#include <stdlib.h>
#include <time.h>

int main(){
	srand((unsigned) time(NULL));  //初始化随机数发生器
	
	int i = rand();  //获得随机数
}

获得 [a, b] 的随机数：

1
int i = rand() % (b - a + 1) + a;

获得更大的随机数：

  • 多次生成随机数，用位运算拼接
  • 将两个随机数相乘

获得 [a, b] 的更大随机数：

生成一个随机数，将随机数除以 RAND_MAX （随机数范围 [0, RAND_MAX]），得到一个 [0, 1] 的浮点数，将其乘以 [b - a] ，再加上 a 。

1
(int)(1.0 * rand() / RAND_MAX * (b - a) + a)

(3) 优化快排

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
int Partition(int A[],int low, int high){

    //增加的两行代码
	int p = (int)(1.0 * rand() / RAND_MAX * (high - low) + low);  //获得随机数
	swap(A[low], A[P]);  //将此随机数指定的数字交换到序列头
	
	
	temp = A[low];
	while (low < high){
		while (A[high] >= temp && low < high)    high--;
		A[low] = A[high];
		while (A[low] <= temp && low < high)    low++;
		A[high] = A[low];
	}
	A[low] = temp;
	return low;
}

void QuickSort(int A[],int low, int high){
	if (low < high){
		int flag = Partition(A, low, high);
		QuickSort(A,low, flag - 1);
		QuickSort(A,flag + 1, high);
	}
}

​

参考

  • 算法笔记