算法设计（分治法应用实验报告）基于分治法的合并排序、快速排序、最近对问题-阿里云开发者社区

一、名称

分治法应用

二、目的

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、小结

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

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

一、名称

二、目的

三、要求

四、内容

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

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

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

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

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

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

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

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

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

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

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

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

4、运行结果

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

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

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

5、小结

热门文章

最新文章

相关课程

相关电子书

探索云世界

热门

云计算

大数据

云原生

人工智能

数据库

开发与运维

活动广场

任务中心

训练营

直播

乘风者计划

下载

镜像站

技术资料

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

一、名称

二、目的

三、要求

四、内容

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

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

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

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

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

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

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

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

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

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

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

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

4、运行结果

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

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

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

5、小结

热门文章

最新文章

相关课程

相关电子书

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