• 算法设计 （分治法应用实验报告）基于分治法的合并排序、快速排序、最近对问题

    一、名称

    分治法应用

    二、目的

    1.掌握分治法的基本思想；
    2.学会运用分治法解决实际系统设计应用中碰到的问题。

    三、要求

    1．实现基于分治法思想的合并排序；
    2．实现基于分治法思想的快速排序；
    3．利用分治法解二维的最近对问题。

    四、内容

    1.实现基于分治法思想的合并排序

    1.1、合并排序的伪代码描述

    Mergesort（A[0,n-1],first,last）
//输入：无序数组A[0,n-1] ,first数组起点,last数组终点
//输出：s升序数组A[0,n-1]

Int mid=(first+last)/2   //寻找中间点划分
Mergesort(A[],0,mid)  //左序列
Mergesort(A[],mid+1,n-1)//右序列
Merge(A[],first,last)  //合并

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8

    1.2、合并排序的源代码实现

    public class Test {

	public static void main(String[] args) {
		test();// 调用静态方法

	}

	/*
	 * 将传入的数组拆分 然后合并
	 */
	public static void mergeSort(int array[], int first, int last, int temp[]) {

		if (first < last) {
			int mid = (first + last) / 2;// 找到中间位置的元素，对数组进行划分
			mergeSort(array, first, mid, temp);// 对左侧数组拆分
			mergeSort(array, mid + 1, last, temp);// 对右侧数组拆分
			sort(array, first, last, mid, temp);// 二路合并
		}

	}

	/*
	 * 对拆分的数组进行合并 按照升序的方式排列，在合并的过程中右侧数组的数据小于左侧贼提前加入新的数组
	 */
	public static void sort(int array[], int first, int last, int mid, int temp[]) {
		int a = first;
		int b = mid;
		int c = mid + 1;
		int d = last;
		int e = 0;// 新数组的下标索引

		while (a <= b && c <= d) {// 保证a的索引是左数组，c是右侧数组的下标
			if (array[a] <= array[c]) {
				temp[e++] = array[a++];// 小的数据放入数组
			} else {
				temp[e++] = array[c++];
			}
		}
		// 两侧数组全部比较结束后，如果左右两侧数组仍有数据，则依次加入新的数组
		while (a <= b) {
			temp[e++] = array[a++];
		}

		while (c <= d) {
			temp[e++] = array[c++];
		}

		// 将辅助数组的值重新给旧的数组
		for (int i = 0; i < e; i++) {
			array[first + i] = temp[i];
		}

	}

	// 测试用例

	public static void test() {

		int N = 8000;
		Random rand1 = new Random();
		int[] array = new int[1000];
		for (int i = 0; i < array.length; i++) {
			array[i] = rand1.nextInt(N);
		}
		int n = array.length;
		int[] temp = new int[n];// 辅助数组

		long startTime = System.currentTimeMillis();// 开始的时间
		mergeSort(array, 0, n - 1, temp);
		System.out.println("\n排序后的数据：");
		int count = 0;
		for (int i = 0; i < n; i++) {
			System.out.print(array[i] + " ");
			count++;
			if (count % 50 == 0) {
				System.out.println("\n");
			}
		}
		long endTime = System.currentTimeMillis();// 结束的时间
		long time = endTime - startTime;
		System.out.println("\n");
		System.out.println("耗时：" + time + "毫秒");

	}

}

    • 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
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86

    1.3 合并排序的时间效率分析

    当待排序的元素只有一个时，T(n)=O(1);
    当n>1时，所需总时间为，拆分元素的时间（查找中间元素的位置）需要时间O（n）。解决子问题，递归求解两个规模为n/2的子问题，所需时间2T（n/2）。n个元素合并，需要O(n)。
    所需总时间为T(n)= 2T（n/2）+ O（n）
    所以时间复杂度为：O(nlogn)

    2.实现基于分治法思想的快速排序

    2.1、快速排序的伪代码描述

    Quicksort(A[l,r]
//输入：数组A[0,n-1]的子数组A[l,r],l,r代表左右下标
//输出：A[l,r]的一个划分，分裂点的位置作为返回值
P←A[l]
i←l+1
j←r
repeat
  repeat i←i+1 until A[i]>=p
  repeat j←j-1 until A[j]<=p
 swap(A[i],A[j])
until i>=j   //基点位置
swap(A[i],A[j])//撤销最后一次交换
swap(A[i],A[j])   分裂点元素交换，完成一次划分
return j

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

    2.2 、快速排序的源代码实现

    public class QuickSort {

	public static void main(String[] args) {
		test();
	}
	
	

	public static void quicksort(int[] A, int l, int r) {
		if (l < r) {
			int p = A[l];// 轴点元素
			int i = l + 1;
			int j = r;
			// 不能写成while(i<=j)。注意i=j的情况，1、1时失效。
			// 因为，i和j都指向第二个1，造成死循环。
			while (true) {
				// i作为指针从左到右扫描,且不能超过j
				while (A[i] < p) {
					i++;
					if (i >= r) {
						break;
					}
				}
				// j作为指针从右到左扫描
				while (A[j] > p) {
					j--;
				}
				if (i < j) {
					swap(A, i, j);
					i++;
					j--;
				} else {
					break;
				}
			}
			// 分裂点条件
			if (i >= j) {
				// j作为分裂点，A[j]与轴点元素交换
				swap(A, l, j);
				quicksort(A, l, j - 1);
				quicksort(A, j + 1, r);
			}
		}

	}

	/**
	 * 交换数组中的元素
	 */
	public static void swap(int A[], int i, int j) {
		int temp = A[i];
		A[i] = A[j];
		A[j] = temp;
	}

	/**
	 * 测试用例
	 */
	public static void test() {

		int N = 8000;
		Random rand1 = new Random();
		int[] array = new int[1000];
		
		for (int i = 0; i < array.length; i++) {
			array[i] = rand1.nextInt(N);
		}
		int n = array.length;
		// 开始时间
		long startTime = System.currentTimeMillis();
		quicksort(array, 0, n - 1);

		int count=0;
		for (int i = 0; i < n; i++) {
			System.out.print(array[i] + " ");
			count++;
			if(count%50==0) {
				System.out.println("\n");
			}
		}
		System.out.println("\n");
		long endTime = System.currentTimeMillis();
		long time = endTime - startTime;
		System.out.println("耗时：" + time + "毫秒");
	}
}

    • 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
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86

    2.3、快速排序的时间效率分析

    快速排序的时间主要耗费在划分操作上，对长度为n的区间进行划分，共需n-1次关键字的比较，时间复杂度为O(n)。

    3．利用分治法解二维的最近对问题

    3.1、解最近对问题的伪代码描述

    算法 EfficientClosestPair(P,Q)
//使用分治法来求解最近对问题
//输入：数组p中存储了平面上的n>=2个点，并且按照这些点的x轴坐标升序排列，数组存储了与p相同的点，按照y轴坐标升序排列

//输出最近点对之间的欧几里得距离

If n<=3
  返回由蛮力算法求出的最小距离
Else
将P的前[n/2]个点复制到P1
将Q的前[n/2]个点复制到Q1
将P中余下的[n/2]个点复制到Pr
将Q中余下的[n/2]个点复制到Qr
  D1←EfficientClosestPair(P1,Q1)
  Dr←EfficientClosestPair(Pr,Qr)
D←min{D1,Dr}
m←p[[n/2]-1]x
将Q中所有|x-m|<D的点复制到数组S[0.num-1]
Dminsq←d*d

For i←0 to num-2 do
  k←i+1
  while k<=num-1 and (S[k].y-S[i].y)* (S[k].y-S[i].y)<dminsq
       dminsq←min(S[k].x-S[i].x)* (S[k].x-S[i].x)+（S[k].y-S[i].y）*（S[k].y-S[i].y）,dminsq)
 k←k+1
return sqrt(dminsq)

    • 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

    3.2、解最近对问题的源代码实现

    package com.search.distance;

import java.util.Scanner;

public class DistanceShort {

	public DistanceShort() {// 构造方法调用函数实现
		complish();
	}

	// 实现最短距离的查找
	public void complish() {
		int x = 0, x1 = 0, x2 = 0, x3 = 0, x4 = 0;// 二维点集合的横坐标
		int y = 0, y1 = 0, y2 = 0;// 二维点集合的纵坐标

		double dis1 = 0, dis2 = 0;// 左侧的最短距离和右侧的最短距离

		System.out.println("输入要生成多少个随机点：");
		Scanner s = new Scanner(System.in);
		int n = s.nextInt();

		int A[][] = new int[n][2];// 保存所有点的位置
		int B[][] = new int[n][2];// 保存中轴左侧的点
		int C[][] = new int[n][2];// 保存中轴右侧的点
		int D[][] = new int[n][2];

		for (int i = 0; i < n; i++) {
			A[i][0] = (int) (Math.random() * 100) + 1;// 生成一百以内的随机数，放入横坐标
		}

		for (int i = 0; i < n; i++) {
			A[i][1] = (int) (Math.random() * 100) + 1;// 生成一百以内的随机数，放入横坐标
		}

		System.out.println("生成的随机点如下：");
		int br = 0;
		for (int i = 0; i < n; i++) {
			System.out.print("(" + A[i][0] + "," + A[i][1] + ")" + " ");
			br++;
			if ((br % 12) == 0) {
				System.out.println("\n");
			}

		}

		// 保证假设的初始最小值足够大，目的是:在进行判断的时候，能够将实际的数据保存到较小的数据。不至于遗漏数据
		int minX = (int) Double.POSITIVE_INFINITY;

		// 保证假设的初始最大值足够小，目的是将数组中的最小值能够加入程序的判断之中
		int maxX = (int) Double.NEGATIVE_INFINITY;

		// 寻找二维点集合中的横坐标极点

		for (int i = 0; i < A.length; i++) {

			if (A[i][0] < minX) {// 如果横坐标的最小值任然比设置的初始最小值小，交换位置
				minX = A[i][0];
			}

			if (A[i][0] > maxX) {// 如果横坐标的最大值任然比设置的初始最大值大，交换位置
				maxX = A[i][0];
			}
		}

		// 寻找中轴位置
		int mid = (minX + maxX) / 2;

		System.out.println("中轴位置：" + mid);
		// 将集合中的点分为左右两边两个集合

		int p = 0, t = 0;

		for (int i = 0; i < n; i++) {
			if (A[i][0] <= mid) { // 保存到中轴左侧集合
				B[p][0] = A[i][0];// 保存横坐标
				B[p][1] = A[i][1];// 保存纵坐标
				p++;
			} else { // 保存到中轴左侧集合
				C[t][0] = A[i][0];// 保存横坐标
				C[t][1] = A[i][1];// 保存纵坐标
				t++;
			}
		}

		// 打印左侧集合
		System.out.println("\n左侧集合的点集合：");
		for (int i = 0; i < p; i++) {
			System.out.print("(" + B[i][0] + "," + B[i][1] + ")" + " ");
			br++;
			if ((br % 12) == 0) {
				System.out.println("\n");
			}

		}
		// 打印右侧集合
		System.out.println("\n右侧集合的点集合：");
		for (int i = 0; i < t; i++) {
			System.out.print("(" + C[i][0] + "," + C[i][1] + ")" + " ");
			br++;
			if ((br % 12) == 0) {
				System.out.println("\n");
			}

		}

		// 寻找左右两侧集合两点之间的最短距离

		int dleft = (int) Double.POSITIVE_INFINITY;// 初始化最短距离为较大的数据
		int dright = (int) Double.POSITIVE_INFINITY;// 目的是保证所有的数据都能够成功比较

		int dx = 0, dy = 0, dz = 0;
		// 左侧最短距离的比较，相邻的两个点
		// 为了保证能够比较所有的点，
		for (int i = 0; i < p - 1; i++) {// 外层循环控制横坐标点的移动
			for (int j = i + 1; j <= p - 1; j++) {// 内层循环控制所有点和第一个点的比较
				dx = (B[j][0] - B[i][0]) * (B[j][0] - B[i][0]) + (B[j][1] - B[i][1]) * (B[j][1] - B[i][1]);
				if (dx < dleft) {
					dleft = dx;// 交换最短距离
					x1 = i;
					x2 = j;// 记录左侧最短距离两个点的横坐标
				}
			}

		}

		// 寻找右侧最短的距离
		for (int i = 0; i < t - 1; i++) {
			for (int j = i + 1; j <= t - 1; j++) {
				dy = (C[j][0] - C[i][0]) * (C[j][0] - C[i][0]) + (C[j][1] - C[i][1]) * (C[j][1] - C[i][1]);
				if (dy < dright) {
					dright = dy;
					x3 = i;// 记录右侧最短距离的两个点的横坐标
					x4 = j;
				}
			}
		}

		if (dleft < dright) {
			dis1 = Math.sqrt(dleft);// 开方
			System.out.println("X坐标中最小距离的连个点：" + "(" + A[x1][0] + "," + A[x1][1] + ")" + " " + "(" + A[x2][0] + ","
					+ A[x2][1] + ")");
			System.out.println("最短距离：" + dis1);
			x = x1;
			y = x2;
		} else {
			dis1 = Math.sqrt(dright);
			System.out.println("X坐标中最小距离的连个点：" + "(" + A[x3][0] + "," + A[x3][1] + ")" + " " + "(" + A[x4][0] + ","
					+ A[x4][1] + ")");
			System.out.println("最短距离：" + dis1);
			x = x3;
			y = x4;
		}

		int q = 0;
		for (int i = 0; i < n; i++) {
			if ((mid - dis1) <= A[i][0] && A[i][0] <= (mid + dis1)) {// 寻找中心线两侧距离中心线最近的点
				D[q][0] = A[i][0];
				D[q][1] = A[i][1];
				q++;

			}
		}

		double mind = Double.POSITIVE_INFINITY;// mind设置为正无穷大,作为比较值
		double dis = 0;
		for (int k = 0; k < q - 1; k++) {
			for (int j = k + 1; j <= q - 1; j++) {
				dis = (D[j][0] - D[k][0]) * (D[j][0] - D[k][0]) + (D[j][1] - D[k][1]) * (D[j][1] - D[k][1]);
				if (dis < mind) {
					mind = dis;
					y1 = k;
					y2 = j;// 记录中轴左右两侧点的最近距离
				}

			}
		}
		dis2 = Math.sqrt(mind);// 中轴两侧开方
		System.out.println("左右两侧集合点最短距离：" + dis1 + "      " + "中轴位置最短：" + dis2);

		if (dis1 < dis2) {
			System.out.println("最短距离分布在中轴一侧:" + dis1);
			System.out.println("两个点：" + "(" + A[x][0] + "," + A[x][1] + ")" + "(" + A[y][0] + "," + A[y][1] + ")");
		} else {
			System.out.println("最短距离位于中轴：" + dis2);
			System.out.println("两个点：" + "(" + A[y1][0] + "," + A[y1][1] + ")" + "(" + A[y2][0] + "," + A[y2][1] + ")");
		}

	}

}

package com.search.distance;

public class TestShortDistance {

	public static void main(String[] args) {

		long startTime=System.currentTimeMillis();//开始的时间
     new DistanceShort();
     long endTime=System.currentTimeMillis();//结束时间
     long time=endTime-startTime;
     System.out.println("\n耗时："+time+"毫秒");
    System.out.println("测试用例60");
	}

}

    • 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
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128
    • 129
    • 130
    • 131
    • 132
    • 133
    • 134
    • 135
    • 136
    • 137
    • 138
    • 139
    • 140
    • 141
    • 142
    • 143
    • 144
    • 145
    • 146
    • 147
    • 148
    • 149
    • 150
    • 151
    • 152
    • 153
    • 154
    • 155
    • 156
    • 157
    • 158
    • 159
    • 160
    • 161
    • 162
    • 163
    • 164
    • 165
    • 166
    • 167
    • 168
    • 169
    • 170
    • 171
    • 172
    • 173
    • 174
    • 175
    • 176
    • 177
    • 178
    • 179
    • 180
    • 181
    • 182
    • 183
    • 184
    • 185
    • 186
    • 187
    • 188
    • 189
    • 190
    • 191
    • 192
    • 193
    • 194
    • 195
    • 196
    • 197
    • 198
    • 199
    • 200
    • 201
    • 202
    • 203
    • 204
    • 205
    • 206

    3.3、解最近对问题的时间效率分析

    无论将问题划分为两个规模减半的子问题，还是合并子问题的解，该算法都只需要线性时间。假设n是2的幂，我们得到算法运行时间的递归式：T(n)=2T(n/2)+f(n) 可以求解得到时间复杂度为T(n)=O(nlogn)

    4、运行结果

    4.1、实现基于分治法思想的合并排序

    在这里插入图片描述

    在这里插入图片描述

    4.2、实现基于分治法思想的快速排序

    在这里插入图片描述
    在这里插入图片描述

    4.3、利用分治法解二维的最近对问题

    在这里插入图片描述

    在这里插入图片描述

    5、小结

    通过本次实验我了解到合并排序、快速排序这两个算法的使用。在进行数据的排序时，只有在合适的情况下选择合适的排序算法才能使效率达到最优。我对分治法有了更加深入的了解，通过把一个大的问题分级减少为若干个子问题，通过对子问题的求解最终达到求解问题的结果。最近对的判断，让我明白了在求解一个问题时，求解问题逻辑的重要性。通过分治法的使用，能够将较难的问题化解为小问题分别求解。

  • 相关阅读:
    debian、ubuntu打包deb包工具，图形界面deb打包工具mkdeb
    1 Java 泛型
    【论文复现】——基于逐点前进法的点云数据精简
    Uniapp云开发（Uniapp入门）
    软件成分分析（SCA）完全指南
    软件设计模式白话文系列（十四）策略模式
    rabbitmq 延时队列和死信队列的分析
    Spring MVC的控制器是不是单例模式
    Gateway入门
    jupyter 切换虚拟环境
  • 原文地址：https://blog.csdn.net/weixin_43304253/article/details/125465253