Algorithm

排序和动态规划

Posted by keys961 on January 30, 2018

数据结构与算法——排序和DP

排序

  • 选择排序(选择最小的交换到最前面): 平均时间O(N^2),最坏时间O(N^2),空间O(1),不稳定
1
2
3
4
5
6
7
8
9
10
11
12
13
14

void selectionSort(int A[], int n)
{
	int min, i, j;
	for(i = 0; i < n; i++)
	{
		min = i;
		for(j = i; j < n; j++)
		{
			if(A[j] < A[min])
				min = j;
		}
		swap(&A[i], &A[min]);
	}
}
  • 冒泡排序(通过邻居两两交换将最大的放在最后面):平均时间O(N^2),最坏时间O(N^2),空间O(1),稳定
1
2
3
4
5
6
7
8
9
10
11
12

void bubbleSort(int A[], int n)
{
	int i = 0, j = n;
	for(int j = n - 1; j >= 0; j--)
	{
		for(int i = 0; i < j; i++)
		{
			if(A[i] > A[i + 1])
				swap(&A[i], &A[i + 1]);
		}
	}
}
  • 插入排序(类似抓扑克牌,选定一个元素,向前扫描把大的向后移,若扫到小的则停止,将元素插入此位置):平均时间O(N^2),最坏时间O(N^2),空间O(1),稳定
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

void insertSort(int[] A, int n)
{
	int temp;
	for(int i = 1; i < n; i++)
	{
		temp = A[i];
		for(int j = i; j > 0; j--)
		{
			if(A[j - 1] > temp)
				A[j] = A[j - 1];
			else
				break;
		}
		A[j] = temp;
	}
}
  • 希尔排序(多步长且步长递减的插入排序):平均时间O(N^d),最坏时间O(N^2),空间O(1),不稳定
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

void shellSort(int A[], int n)
{
	int temp;
	for(int step = n / 2; step > 0; step /= 2)
	{
		for(int i = step; i < n; i += 1) //insertion sort with step >= 1
		{
			temp = A[i];
			for(int j = i; j > 0; j -= step)
			{
				if(A[j - step] > temp)
					A[j] = A[j - step];
				else
					break;
			}
			A[j] = temp;
		}
	}
}
  • 堆排序(建立二叉堆,升序则建立最大堆):平均时间O(NlogN),最坏时间O(NlogN),空间O(1),不稳定
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
26
27
28
29
30
31
32
33
34
35

void buildHeap(int A[], int n)
{
	int lastNotLeaf = (n - 1) / 2;
	for(int i = lastNotLeaf; i >= 0; i--)
		percDown(A, n, i);
}

void percDown(int A[], int n, int index)
{
	int child, i;
	int temp = A[index];
	for(i = index; 2 * i + 1 < n; i = child)
	{
		child = 2 * i + 1;
		if(child < n - 1 && A[child] < A[child + 1])
			child++;
		if(temp < A[child])
			A[i] = A[child];
		else
			break;
	}
	A[i] = temp;
}

void heapSort(int A[], int n)
{
	buildHeap(A, n); //O(N)
	int size = n;
	for(int i = 0; i < n; i++)//O(NlogN)
	{
		swap(&A[0], &A[size - 1]);
		size--;
		percDown(A, size, 0);
	}
}
  • 归并排序(分治法,两个有序数列的归并):平均时间O(NlogN),最坏时间O(NlogN),空间O(N),稳定
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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

void merge(int A[], int temp[], int leftStart, int rightStart, int rightEnd)
{
	int leftEnd, numElements, tmpPos;
	leftEnd = rightStart - 1;
	tmpPos = leftStart;
	numElements = rightEnd - leftStart + 1;
	while(leftStart <= leftEnd && rightStart <= rightEnd)
	{
		if(A[leftStart] <= A[rightStart])
			temp[tmpPos++] = A[leftStart++];
		else
			temp[tmpPos++] = A[rightStart++];
	}
	
	while(leftStart <= leftEnd)
		temp[tmpPos++] = A[leftStart++];
	while(rightStart <= rightEnd)
		temp[tmpPos++] = A[rightStart++];
	
	for(int i = 0; i < numElements; i++, rightEnd--)
		A[rightEnd] = temp[rightEnd];
}

void mSort(int A[], int temp[], int left, int right)
{
	int center = (left + right) / 2;
	if(left < right)
	{
		mSort(A, temp, left, center);
		mSort(A, temp, center + 1, right);
		merge(A, temp, left, center + 1, right);
	}
}

void mergeSort(int A[], int n)
{
	int* temp = (int*)malloc(sizeof(int) * n);
	mSort(A, temp, 0, n - 1);
	free(temp);
}
  • 快速排序(分治法,找Pivot,左边比Pivot小,右边比Pivot大):平均时间O(NlogN),最坏时间O(N^2),空间O(logN),不稳定
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

void qSort(int A[], int left, int right)
{
	if(left >= right)
		return;

	int pivot = A[right];
	int i = left, j = left;

	for(; j < right; j++)
	{
		if(A[j] <= pivot)
		{
			swap(&A[i], &A[j])
			i++;
		}
	}
	swap(&A[right], &A[i]);
	qSort(A, left, i - 1);
	qSort(A, i + 1, right);
}

void quickSort(int A[], int n)
{
	qSort(A, 0, n - 1);
}
  • 基数排序/桶排序:平均时间O(P(N+B)),最坏时间O(P(N+B)),空间O(N+B),稳定

动态规划

  1. 线性递推

    线性递推式

    例:爬楼梯问题,一次爬1或2步,对于n步有多少走法

    f(n)=f(n-1)+f(n-2), f(0)=f(1)=1

    此外类似的有Fibonacci序列.

  2. 钢条切割问题

    给定长度i以及对应长度的价格p[i],给定长度为n的钢条,则求最大收益.

    状态转移方程:r[n]=max{p[i]+r[n-i]} 1<=i<=n(即钢条左边切下i,且左边不再分割,右边的n-i继续递归切割)

  3. 矩阵链乘法

    给定矩阵链乘法,求解相乘的顺序使计算代价最小.

    对于矩阵A[i],其规模为p[i-1]*p[i], i>=1.

    状态转移方程:

    • 若i=j,M[i][j]=0;若i<j,则M[i][j]=min{M[i][k]+M[k+1][j]+p[i-1]p[k]p[j]},i<=k<j

      (这里1<=i,j<=n,M[i][j]表明第i个矩阵到第j个矩阵连续相乘的最小代价.)

    即(按M[1][1],M[2][2],..,M[1][2],M[2][3],...M[1][3],M[2][4],..M[1][N]顺序算):

    1
2
3
4
5
6
7
8
9
10
11
12
13

    for(int i = 1; i <= n; i++)
 M[i][i] = 0;
for(int step = 1; step < n; step++)
{
 for(int i = 1; i <= n; i++)
 {
     int j = i + step;
     for(int k = i; k < j; k++)
         M[i][j] = min(M[i][j],
         M[i][k] + M[k+1][j] 
         + p[i-1]*p[k]*p[j]);
 } 
}

  4. 最长公共子序列(LCS)

    给定字符串X=<x1,...,xn>和Y=<y1,...,ym>,求最长公共的子序列.

    令c[i][j]为X[:i]和Y[:j]最长子序列长度,则转移方程为:

    • 若i=0或j=0,c[i][j]=0

    • 若X[i]=Y[j],c[i][j]=c[i-1][j-1]+1

    • 否则c[i][j]=max{c[i-1][j],c[i][j-1]}

    变种:最长回文子序列——只要求给定串str和它的逆序串rev(str)的LCS即可

  5. 最优二叉搜索树

    给定有序序列K=<k1,...,kn>以及对应的搜索频率P=<p1,...,pn>.记c[i][j]为第i个元素到第j个元素构成的二叉搜索树的搜索开销,w[i][j]为第i个元素到第j个元素的总权重(=p[i]+...+p[j])

    则状态转移方程为:

    • c[i][j]=max{p[k]+c[i][k-1]+c[k+1][j]+w[i][k-1]+w[k+1][j]},也即为c[i][j]=max{w[i][j]+c[i][k-1]+c[k+1][j]} (i<k<=j),计算顺序和矩阵链乘法类似(O(N^3),可优化为O(N^2))

  6. 多源最短路径——Floyd算法

    D[i][j]:从节点i到j的最短距离,初始化为邻接矩阵的值(若无直接的边则为正无穷大,若i=j则初始化为0)

    状态转移方程:

    • D[i][j]=max{D[i][k]+D[k][j]}, i<=k<=j,并可记录path[i][j]=k表示i到j比经过k

  7. 最长上升子序列(LIS)

    给定N个数，求这N个数的最长上升子序列的长度

    即I[i]为从第1个到第i个数的最长上升子序列长度,则状态转移方程为(可优化到O(NlogN)):

    • 若a[j]<a[i]则I[i]=max{I[j]}+1, 1<=j<i.

    • 若前面没有比a[i]小的,则I[i]=1

  8. 0-1背包/完全背包问题

    给定N件物品,一个容量为V的背包,第i件物品的大小为w[i],价值为p[i],求背包可装的价值最大值.

    记f[i][j]为可选的从第1~i个物品里,容量为j的背包可装的最大价值.

    • 0-1背包:东西不可分割,每件物品只有一件.状态转移方程易得为:

      • f[i][j]=max{f[i-1][j],f[i-1][j-w[i]]+p[i]},式子中max{}第二项只有j-w[i]>=0时才能计算.

    • 完全背包:东西不可分割,物品件数无限.状态转移方程只需稍稍修改(i-1=>i)即可:

      • f[i][j]=max{f[i-1][j],f[i][j-w[i]]+p[i]},式子中max{}第二项只有j-w[i]>=0时才能计算.

    • 多重背包问题:东西不可分割,物品件数有限.我们可以将其转化成0-1背包,将相同的物品视作不同的物体即可,然后套用0-1背包问题的解法.

CATALOG
    FEATURED TAGS
    Algorithm Java Network Distributed System Stream Processing Operating System Paper Linux Redis etcd Kubernetes C++