AI 助理
备案控制台
开发者社区 人工智能 文章 正文

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

2024-08-15 42
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 这篇文章是关于分治法应用的实验报告，详细介绍了如何利用分治法实现合并排序和快速排序算法，并探讨了使用分治法解决二维平面上的最近对问题的方法，包括伪代码、源代码实现及时间效率分析，并附有运行结果和小结。

一、名称

分治法应用

二、目的

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、合并排序的源代码实现

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.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

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 + "毫秒");
    }
}

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)

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");
    }

}

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

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

4、运行结果

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

在这里插入图片描述

在这里插入图片描述

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

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

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

在这里插入图片描述

在这里插入图片描述

5、小结

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

文章标签：
算法
搜索推荐
关键词：
算法应用
算法快速排序
算法排序
算法实验
算法分治快速排序
热爱技术的小郑
目录
相关文章
ephemerals__
|
1月前
|
搜索推荐 C语言
【排序算法】快速排序升级版--三路快排详解 + 实现（c语言）
本文介绍了快速排序的升级版——三路快排。传统快速排序在处理大量相同元素时效率较低，而三路快排通过将数组分为三部分（小于、等于、大于基准值）来优化这一问题。文章详细讲解了三路快排的实现步骤，并提供了完整的代码示例。
ephemerals__
57 4
众所周知
|
2月前
|
存储 算法 Java
解析HashSet的工作原理，揭示Set如何利用哈希算法和equals()方法确保元素唯一性，并通过示例代码展示了其“无重复”特性的具体应用
在Java中，Set接口以其独特的“无重复”特性脱颖而出。本文通过解析HashSet的工作原理，揭示Set如何利用哈希算法和equals()方法确保元素唯一性，并通过示例代码展示了其“无重复”特性的具体应用。
众所周知
54 3
德国都芳最好
|
22天前
|
存储 搜索推荐 Python
用 Python 实现快速排序算法。
快速排序的平均时间复杂度为$O(nlogn)$，空间复杂度为$O(logn)$。它在大多数情况下表现良好，但在某些特殊情况下可能会退化为最坏情况，时间复杂度为$O(n^2)$。你可以根据实际需求对代码进行调整和修改，或者尝试使用其他优化策略来提高快速排序的性能
德国都芳最好
115 61
代码bug生产队
|
22天前
|
机器学习/深度学习 人工智能 算法
探索人工智能中的强化学习：原理、算法与应用
探索人工智能中的强化学习：原理、算法与应用
代码bug生产队
43 3
龙大吉
|
21天前
|
机器学习/深度学习 算法 数据挖掘
C语言在机器学习中的应用及其重要性。C语言以其高效性、灵活性和可移植性，适合开发高性能的机器学习算法，尤其在底层算法实现、嵌入式系统和高性能计算中表现突出
本文探讨了C语言在机器学习中的应用及其重要性。C语言以其高效性、灵活性和可移植性，适合开发高性能的机器学习算法，尤其在底层算法实现、嵌入式系统和高性能计算中表现突出。文章还介绍了C语言在知名机器学习库中的作用，以及与Python等语言结合使用的案例，展望了其未来发展的挑战与机遇。
龙大吉
39 1
土木林森
|
21天前
|
并行计算 算法 测试技术
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略，涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略，涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面，旨在通过综合策略提升程序性能，满足实际需求。
土木林森
49 1
wljslmz
|
1月前
|
缓存 算法 网络协议
OSPF的路由计算算法：原理与应用
OSPF的路由计算算法：原理与应用
wljslmz
45 4
游客wzls46nubyw7c
|
28天前
|
机器学习/深度学习 监控 算法
基于反光衣和检测算法的应用探索
本文探讨了利用机器学习和计算机视觉技术进行反光衣检测的方法，涵盖图像预处理、目标检测与分类、特征提取等关键技术。通过YOLOv5等模型的训练与优化，展示了实现高效反光衣识别的完整流程，旨在提升智能检测系统的性能，应用于交通安全、工地监控等领域。
游客wzls46nubyw7c
36 1
一位隐者
|
1月前
|
存储 算法 网络协议
OSPF的SPF算法介绍：原理、实现与应用
OSPF的SPF算法介绍：原理、实现与应用
一位隐者
76 3
ephemerals__
|
1月前
|
搜索推荐 算法 C语言
【排序算法】八大排序（上）（c语言实现）（附源码）
本文介绍了四种常见的排序算法：冒泡排序、选择排序、插入排序和希尔排序。通过具体的代码实现和测试数据，详细解释了每种算法的工作原理和性能特点。冒泡排序通过不断交换相邻元素来排序，选择排序通过选择最小元素进行交换，插入排序通过逐步插入元素到已排序部分，而希尔排序则是插入排序的改进版，通过预排序使数据更接近有序，从而提高效率。文章最后总结了这四种算法的空间和时间复杂度，以及它们的稳定性。
ephemerals__
94 8

热门文章

最新文章

  • 1
    领域最全 | 计算机视觉算法在路面坑洼检测中的应用综述(基于2D图像/3D LiDAR/深度学习)（下）
  • 2
    DL之ANN/DNN： 人工神经网络ANN/DNN深度神经网络算法的简介、应用、经典案例之详细攻略
  • 3
    iOS 算法之排序、查找、递归
  • 4
    openssl中算法的组织方式
  • 5
    智能解决装箱问题：使用优化算法实现高效包装
  • 6
    指针难，算法难，难住了谁
  • 7
    多视图立体视觉: CVPR 2019 与 AAAI 2020 上的ACMH、ACMM及ACMP算法介绍
  • 8
    Linux内核中的有关Page的算法
  • 9
    OpenCV 1 图像分割--分水岭算法代码
  • 10
    缓存、缓存算法(转)
  • 1
    BASE64的算法说明
    68
  • 2
    算法人生（1）：从“强化学习”看如何“战胜拖延”
    114
  • 3
    理解并应用机器学习算法：决策树
    145
  • 4
    【机器学习】在使用K-means聚类算法时，如何选择K的值？
    412
  • 5
    【机器学习】为什么K-means算法使用欧式距离度量？
    396
  • 6
    【机器学习】描述K-means算法的步骤
    153
  • 7
    【机器学习】K-means和KNN算法有什么区别？
    640
  • 8
    C语言易混淆、简单算法、结构体题目练习、常见关键字总结-2
    54
  • 9
    C语言易混淆、简单算法、结构体题目练习、常见关键字总结-1
    57
  • 10
    图搜索算法详解
    138

    • 相关课程

    更多
  • 智能运维赛（复赛）：利用数据和算法，快速定位系统异常并进行根因分析
  • 智能创作赛（复赛）：相册应用中的视频故事生成算法介绍
  • 智能创作赛（初赛）：相册应用中的故事生成算法介绍
  • 相册服务中的故事生成算法介绍
  • Go语言核心编程 - 数据结构和算法
  • 神经网络概览及算法详解

    • 相关电子书

    更多
  • 数据+算法定义新世界
  • 袋鼠云基于实时计算的反黄牛算法
  • Alink：基于Apache Flink的算法平台

    • 相关实验场景

    更多
  • 使用Swing算法实现商品推荐
  • RSA密码算法设计与实现
  • RSA非对称加密算法
  • 欧拉图的构造性证明与算法实现
  • 推荐系统入门之使用ALS算法实现打分预测
    • 下一篇
    DataWorks