算法设计与分析

发表于 | 分类于 |

课上所学，课下实现，顺便学下Java

1 归并排序

1.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
public class Merge {
    private static Comparable[] aux;    //归并排序需要的数组

    public static void sort(Comparable[] a)
    {
        aux = new Comparable[a.length];
        sort(a, 0, a.length-1);
    }

    public static void sort(Comparable[] a, int lo, int hi)
    {
        if(hi <= lo)    return;
        int mid = lo + (hi - lo)/2;
        sort(a, lo, mid);
        sort(a, mid+1, hi);
        merge(a, lo, mid, hi);
    }

    public  static void merge(Comparable[] a, int lo, int mid,int hi)
    {//将a[lo..mid] 和 a[mid+1..hi]归并
        int i = lo, j = mid + 1;

        for (int k = lo; k<=hi; k++)   //将a[lo..hi]复制到aux[lo..hi]
            aux[k] = a[k];
        for (int k = lo; k<=hi; k++)   //归并
            if(i > mid)                   a[k] = aux[j++];
            else if(j > hi)               a[k] = aux[i++];
            else if(less(aux[i],aux[j]))  a[k] = aux[i++];
            else                          a[k] = aux[j++];
    }

    private static boolean less(Comparable v, Comparable w)
    { return v.compareTo(w) < 0; }
}

1.11 对小规模子数组使用插入排序

因为递归会使小规模问题中的递归调用过于频繁，所以改进对他们的处理就能改进整个算法。插入排序很可能在小数组上比归并排序更快。

1.12 测试数组是否已经有序

添加一个判断条件，如果a[mid]小于等于a[mid+1]，我们就认为数组是已经有序的，并跳过merge()方法。

1.13 将不重复元素复制到数组

1.2 自底向上的归并排序

这个merge的地方很巧妙,感觉这种写法更清晰一点，下面那种用while的我自己都快把自己绕晕了

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
public class MergeBU {
     private static boolean less(Comparable v, Comparable w)
    { return v.compareTo(w) < 0; }

    private static Comparable[] aux;

    public static void sort(Comparable[] a)
    {//进行logN次两两归并
        int N = a.length;
        aux = new Comparable[N];
        for(int sz = 1; sz <N; sz = sz + sz)         //sz子数组大小
            for(int lo = 0; lo < N-sz; lo += sz + sz)// lo:子数组索引
                merge(a, lo, lo + sz-1, Math.min(lo+sz+sz-1, N-1));
    }
     public  static void merge(Comparable[] a, int lo, int mid,int hi)
    {//将a[lo..mid] 和 a[mid+1..hi]归并
        int i = lo, j = mid + 1;

        for (int k = lo; k<=hi; k++)   //将a[lo..hi]复制到aux[lo..hi]
            aux[k] = a[k];
        for (int k = lo; k<=hi; k++)   //归并
            if(i > mid)                   a[k] = aux[j++];
            else if(j > hi)               a[k] = aux[i++];
            else if(less(aux[i],aux[j]))  a[k] = aux[i++];
            else                          a[k] = aux[j++];
    }
}

自己用C写的

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
41
42
43
44
void Merge(int *A,int start,int mid, int end)
{
	int B[end - start + 1] = {0};
	int s = start, t = mid+1, k = start;
	while(s <= mid && t<=end){
		if(A[s] <= A[t])
			B[k++ - start] = A[s++];   //这里这个 -start坑了我好长时间 
		else
			B[k++ - start] = A[t++];
	}
	int j = k;
    //这里是个优化,可以减少赋值次数 
	while(s <= mid)
		A[j++] = A[s++];
	for(int i=start; i<=k-1; i++)
		A[i] = B[i - start];
	return;
}
void BottomupSort(int *A, int n)
{
	int t = 1;
	while(t<=n){
		int s ,i;
		i = 0;
		s = t;
		t = s*2;
		while(i + t <=n){
			Merge(A,i,i+s-1,i+t-1);
			i = i+t;
		}
		if(i+s < n){
			Merge(A,i,i+s-1,n-1);
		}
	}
}
int main()
{
	int A[10] = {4,1,7,5,8,2,6,3,10,9};
	BottomupSort(A,10);
	for(int i=0; i<=9; i++)
		printf("%d ",A[i]);
	
	return 0;
 }

2 堆实现的优先队列

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
package com.company;

import java.util.EmptyStackException;

public class MaxPQ<Key extends Comparable<Key>> {
    private Key[] pq;       //基于堆的完全二叉树
    private  int N = 0;     //存储于pq[1...N]，pq[0]并没有使用

    public MaxPQ(int maxN)
    {  pq = (Key[]) new Comparable[maxN + 1]; }
    public boolean isEmpty()
    {  return N == 0; }
    public int size()
    {
        return N;
    }
    public void insert(Key v)
    {
        pq[++N] = v;
        swim(N);
    }
    public Key delMax()
    {
        Key max = pq[1];        //从根节点得到最大元素
        exch(1,N--);         //将其和最后一个元素交换
        pq[N+1] = null;         //防止对象游离
        sink(1);            //恢复堆上的有序性
        return max;
    }
    private boolean less(int i, int j)
    {  return pq[i].compareTo(pq[j]) < 0; }

    private void exch(int i, int j)
    {  Key t = pq[i]; pq[i] = pq[j]; pq[j] = t;}

    private void swim(int k)            //上浮
    {
        while( k > 1 && less(k/2, k))
        {
            exch(k/2, k);
            k = k/2;
        }
    }

    private void sink(int k)       //下沉
    {
        while(2*k <= N)
        {
            int j = 2*k;
            if(j < N && less(j, j+1))   j++;
            if(!less(k, j)) break;
            exch(k,j);
            k = j;
        }
    }
}

3 快速幂

思路类似于多项式求和

1
2
3
4
5
6
7
8
9
10
11
12
int pow2(int i, int j)
{
	int result = 1, n, s = i;
	while(j){
		n = j%2;
		j = j/2;
		if(n == 1)
			result *= s;
		s *= s;
	}
	return result;
}

4 求多数元素

在原序列中去除两个不同的元素以后，原序列中的多数元素在新的序列中还是多数元素O(n)的时间复杂度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int majorityElement(int *a,int len)
{
	int count = 1;
	int maj = a[0];
	for(int i=1; i<len; i++){
		if(maj == a[i])
			count++;
		else{
			count--;
			if(count == 0){
				maj = a[i+1];
			}
		}
	}
	return maj;
}

5分治

5.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
/*寻找最小值需要进行n-1次比较，这已经是最优结果。如果需要同时找出最大值和最小值，可以直接进行两次查询，
一次最大值一次最小值，共需要2(n-1)次比较。而事实上，我们可以只通过3*[n/2]次比较就足以同时找到最大值和最小值。
通过成对的处理元素，先将一对输入元素比较，找到较大值和较小值。然后将较大值与当前最大值比较，较小值与当前最小值比较，
这样每两个元素需要比较3次，一共需要3*[n/2]次比较。
*/
void max_min(int a[], int l, int r, int &minValue, int &maxValue)
{
	if (l == r) {// l 与 r之间只有一个元素
		minValue = maxValue = a[l];
		return; 
	}
	if (l + 1 == r){ // l 与 r 之间只有两个元素
	    if(a[l] > a[r]){
	    	minValue = a[r];
	    	maxValue = a[l];
		} 
		else{
			minValue = a[l];
			maxValue = a[r];
		}
		return;
	}
	int lmax,  lmin;
	int m = (l + r)/2;
	max_min(a, l, m, lmin, lmax); //找出左边最大值和最小值 
	int rmax ,rmin;
	max_min(a, m+1, r, rmin, rmax); // 找出右边最大值和最小值 
	maxValue = max(lmax, rmax);
	minValue = min(lmin, rmin); 
}

5.2 求第k小元素

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
41
42
//划分——每次划分唯一确定一个元素位置
int partition(int A[], int low, int high)
{
	int pivot = A[low];
	while(low < high){
		while(low < high && A[high] >= pivot){
			--high;
		}
		A[low] = A[high]; //将比基准小的元素移动到左端
		while(low < high && A[low] <= pivot){
			++low;
		} 
		A[high] = A[low];
	}
	A[low] = pivot;
	return low;
}

int r = 5;

int select_rank_k(int A[], int low, int high, int k)
{
	int r_group = ceil((high - low + 1) * 1.0 / r); //ceil 取上限共分为r_group个组
	//计算每个分组中值，存于A[]最前面
	for (int i = 1; i <= r_group; ++i){
		sort(&A[low + (i - 1)*r], &A[(low + i*r -1) > high ? high: (low + i*r - 1)]);
		swap(A[low + i - 1], A[low + (i-1)*r + r/2]);
	}
	//获得每个组的中值的中值（并置于A[low]位置，方便调用快排划分函数)
	sort(&A[low], &A[low + r_group]);
	swap(A[low], A[low + r_group /2]);
	int cur = partition(A, low, high);
	if( cur == k-1){
		return A[cur];
	} 
	else if ( cur < k){
		return select_rank_k(A, cur + 1,  high, k);
	}
	else {
		return select_rank_k(A, low, cur - 1, k);
	}
}

6 动态规划

6.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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include<stdio.h>
#include <string.h>
#include <algorithm>
#define MAXLEN 50
using namespace std;
void LCSLength(char *x, char *y, int m, int n, int c[][MAXLEN])
{
	for(int i=0; i<=m; i++)
		c[i][0] = 0;
	for(int i=0; i<=n; i++)
		c[0][i] = 0;
	for(int i=1; i<=m; i++){
		for(int j=1; j<=n; j++){
			if(x[i-1] == y[j-1]){
				c[i][j] = c[i-1][j-1] + 1;
			}
			else{
				c[i][j] = max(c[i-1][j],c[i][j-1]);
			}
		}
	}
	return;	
}
void printLCS(int c[][MAXLEN], int i, int j,char *x)
{
	char s[MAXLEN];
	int k = c[i][j];
	s[k] = '\0';
	while(k>0){
		if(c[i][j] == c[i-1][j]) i--;
		else if (c[i][j] == c[i][j-1]) j--;
		else{
			s[--k] = x[i-1];
			i--;
			j--;
		}
	}
	printf("%s",s);
}
int main() 
{
	char x[MAXLEN] = {"ABCBDAB"};
    char y[MAXLEN] = {"BDCABA"};
    int c[MAXLEN][MAXLEN];
    int m = strlen(x);
    int n = strlen(y);
    LCSLength(x,y,m,n,c);
    printf("%d\n",c[m][n]);
    printLCS(c, m, n, x);
	return 0;
}

6.2 背包问题

问题描述：

有N件物品和一个容量为V的背包。第i件物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使价值总和最大。

基本思路 ：

这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。 用子问题定义状态：即f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。则其状态转移方程便是：

代码如下

1
2
3
4
5
6
7
8
for(int i = 1; i <= n; i++)
    {
        for(int j = 0; j <= W; j++)
        {
            if(j < w[i])    dp[i][j]  = dp[i-1][j];
            else dp[i][j] =  max(dp[i-1][j], dp[i-1][j - w[i]] + v[i]);
        }
    }

优化空间复杂度：

以上方法的时间和空间复杂度均为O(VN)，其中时间复杂度应该已经不能再优化了，但空间复杂度却可以优化到O(V)

只用一维数组的话要注意到，每次他都会利用上一行左边的值，那么我们只要每行从右向左遍历，那么就不会覆盖到原来的值了。

1
2
3
4
5
for(int i = 1; i <= n; i++)
{
 for(int j = W; j >= w[i]; j--)
    dp[j] = max(dp[j], dp[j - w[i] + v[i]);
}
-------------本文结束感谢您的阅读-------------
+ +