算法概论实验一

发表于 | 分类于 
1
2
3
4
5
6
7
8
9
10
11
12
13
实验一

实验目的与要求：理解分治法的基本思想和设计方法。

实验题目：

1．实现基于分治法的归并排序算法.

2. 实现快速排序的算法,并尝试采用不同的方法实现线性的划分过程.

3. 有一个数的序列A[1]、A[2] 、A[3] 、…… 、A[n]，若i<j，并且A[i]>A[j]，则称A[i]与A[j]构成了一个逆序对，设计算法求数列A中逆序对的个数.

4.(选做题) 引入逆序计数问题作为考察两个序列有多大差别的一个好的度量指标。但是人们可能感觉这个量度太敏感了。如果i<j，并且A[i]>2A[j]，我们把这对i,j叫做重要的逆序。设计一个O(nlogn) 的算法计数在两个序列中的重要逆序个数。

##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
package test_chen_921;

public class MergeSort {

	public static void main(String[] args) {
		int[] r = { 5,2,1,0};
		merge_sort(r, 0, r.length - 1);
		print(r);
	}

	private static void print(int[] r) {
		// TODO 打印数组
		for (int i : r) {
			System.out.print(" " + i);
		}
		System.out.println();
	}

	private static void merge_sort(int[] r, int low, int high) {
		// TODO  划分 合并
		if (low < high) {
			int mid = (low + high) / 2;
			merge_sort(r, low, mid);
			merge_sort(r, mid + 1, high);
			merge(r, low, mid, high);
		}
	}

	private static void merge(int[] r, int low, int mid, int high) {
		// TODO  归并两个有序数组
		int k = 0;
		int i = low;
		int j = mid + 1;
		int[] tmp = new int[high - low + 1];
		while (i <= mid && j <= high) {
			if (r[i] <= r[j])
				tmp[k++] = r[i++];
			else
				tmp[k++] = r[j++];
		}
		while (i <= mid)
			tmp[k++] = r[i++];
		while (j <= high)
			tmp[k++] = r[j++];
		for (int m : tmp)
			r[low++] = m;
	}
}

##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
package test_chen_921;

public class quick_test {

	public static void main(String[] args) {
		int[] r = { 5, 8, 6, 4, 2, 3, 1, 7, 9, 0 };
		quick_sort(r, 0, r.length - 1);
		print(r);
	}

	private static void print(int[] r) {
		// TODO 打印数组
		for (int i : r) {
			System.out.print(" " + i);
		}
		System.out.println();
	}

	private static void quick_sort(int[] r, int low, int high) {
		// TODO 找中值，并左右递归
		if (low < high) {
			int mid = partion(r, low, high);
			// print(r);
			quick_sort(r, low, mid);
			quick_sort(r, mid + 1, high);
		}
	}

	private static int partion(int[] r, int low, int high) {
		// TODO 把数组段第一个数划分，并返回中间值的下标
		int pivot = r[low];// 记录pivot
		while (low < high) {
			while (low < high && r[high] > pivot)
				high--;
			if (low < high)
				r[low++] = r[high];
			while (low < high && r[low] < pivot)
				low++;
			if (low < high)
				r[high--] = r[low];
		}
		r[low] = pivot;
		return low;
	}
}

##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
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
57
58
59
60
61
62
63
package test_chen_921;

public class InverseNum {
	
	public static void main(String[] args) {
		int []r = {80, 70, 9,9};
		System.out.println(getInverseNum(r, 0, r.length-1));
	}

	private static int getInverseNum(int[] r, int low, int high) {
		// TODO 计算前一半的逆序数，计算后一半的逆序数，计算之间的逆序数，相加并返回
		if(low<high)
		{
			int mid=(low+high)/2;
			int front_num=getInverseNum(r,low,mid);
			int behind_num=getInverseNum(r,mid+1,high);
			int between_num=mergeInverseNum(r,low,mid,high);
			return front_num+behind_num+between_num;
		}
		return 0;
	}

	private static void print(int[] r) {
		// TODO 打印数组
		for (int i : r) {
			System.out.print(" " + i);
		}
		System.out.println();
	}

	

	private static int mergeInverseNum(int[] r, int low, int mid, int high) {
		// TODO 与归并排序一致
		int []tmp=new int[high-low+1];
		int k1=low;
		int k2=mid+1;
		int k3=0;
		int count=0;
		while(k1<=mid && k2<=high)
		{
			if(r[k1]<=r[k2])
				tmp[k3++]=r[k1++];
			else
			{
				tmp[k3++]=r[k2++];
				//一旦这个数(r[k1])大于r[k2]，那么他后面的数必定大于r[k2]；所以count来源于他后面的数目的个数。
				count += mid - k1 + 1; 
			}
			
		}
		
		while(k1<=mid)
			tmp[k3++]=r[k1++];
		while(k2<=high)
			tmp[k3++]=r[k2++];
		
		for(int m : tmp)
			r[low++]=m;
		
		return count;
	}
}

##4 重要逆序数

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
57
58
59
60
61
62
63
64
65
66
67
68
package test_chen_921;

public class SignificantNum {

	public static void main(String[] args) {
		int[] r = { 80, 70, 9, 9 };
		System.out.println(getSignificantNum(r, 0, r.length - 1));
	}

	private static int getSignificantNum(int[] r, int low, int high) {
		// TODO 计算前一半的逆序数，计算后一半的逆序数，计算之间的逆序数，相加并返回
		if (low < high) {
			int mid = (low + high) / 2;
			int front_num = getSignificantNum(r, low, mid);
			int behind_num = getSignificantNum(r, mid + 1, high);
			int between_num = mergeSig	nificantNum(r, low, mid, high);
			return front_num + behind_num + between_num;
		}
		return 0;
	}

	private static void print(int[] r) {
		// TODO 打印数组
		for (int i : r) {
			System.out.print(" " + i);
		}
		System.out.println();
	}

	private static int mergeSignificantNum(int[] r, int low, int mid, int high) {
		// TODO 先记数，后排序
		int[] tmp = new int[high - low + 1];
		int k1 = low;
		int k2 = mid + 1;
		int k3 = 0;
		int count = 0;

		// count
		while (k1 <= mid && k2 <= high) {
			if (r[k1] <= 2 * r[k2])
				k1++;
			else {
				count += mid - k1 + 1;
				k2++;
			}
		}

		// merge
		k1 = low;
		k2 = mid + 1;
		while (k1 <= mid && k2 <= high) {
			if (r[k1] <= r[k2])
				tmp[k3++] = r[k1++];
			else
				tmp[k3++] = r[k2++];
		}

		while (k1 <= mid)
			tmp[k3++] = r[k1++];
		while (k2 <= high)
			tmp[k3++] = r[k2++];

		for (int m : tmp)
			r[low++] = m;

		return count;
	}
}