分治法求最大值和最小值（Java实现）

已知 n 个无序的元素序列，要求编写一个算法，求该序列中的最大元素和最小元素。

对于无序序列 a[start…end]，可采用分而治之的方法（将问题规模缩小为 k 个子问题加以解决）求最大元素和最小元素。该问题可分为以下几种情况：
1) 若序列 a[start…end] 中只有一个元素，则最大元素和最小元素均为 a[start]。

2) 若序列 a[start…end] 中有两个元素，则最大元素为 a[start] 和 a[end] 中的较大者，最小元素为 a[start] 和 a[end] 中的较小者。

3) 若序列 a[start…end] 中的元素个数超过 2 个，则从中间位置 mid=(start+end)/2 将该序列分为两部分：a[start…mid] 和 a[mid+1…end]。然后分别通过递归调用的方式得到两个区间中的最大元素和最小元素，其中，左边区间求出的最大元素和最小元素分别存放在 m1 和 n1 中，右边区间求出的最大元素和最小元素分别存放在 m2 和 n2 中。

若 m1≤m2，则最大元素为 m2，否则最大元素为 m1；若 n1≤n2，则最小元素为 n1，否则最小元素为 n2。

算法实现如下：

class MaxMinNode {
    int max, min;
    MaxMinNode() {
    }
    MaxMinNode(int m, int n) {
        max = m;
        min = n;
    }
    void SetMax(int m) {
        max = m;
    }
    void SetMin(int n) {
        min = n;
    }
    int GetMax() {
        return max;
    }
    int GetMin() {
        return min;
    }
}

public class MaxMinNum {
    int max, min;

    public static void main(String args[]) {
        int a[] = {65, 32, 78, -16, 90, 55, 26, -5, 8, 41};
        int length = a.length;
        MaxMinNum MMN = new MaxMinNum();
        MaxMinNode resultNode = MMN.Max_Min_Comm(a, length);
        System.out.println("元素序列:");
        for (int i = 0; i < length; i++) {
            System.out.printf("%4d ", a[i]);
        }
        System.out.println();
        System.out.printf("普通比较算法: Max=%4d, Min=%4d\n", resultNode.GetMax(), resultNode.GetMin());
        MaxMinNode Node = MMN.Max_Min_Div(a, 0, length - 1);
        System.out.printf("分治算法: Max=%4d, Min=%4d\n", Node.GetMax(), Node.GetMin());
    }

    MaxMinNode Max_Min_Comm(int a[], int n) {
        int i;
        int min = a[0];
        int max = a[0];
        for (i = 0; i < n; i++) {
            if (a[i] > max)
                max = a[i];
            if (a[i] < min)
                min = a[i];
        }
        MaxMinNode Node = new MaxMinNode();
        Node.SetMax(max);
        Node.SetMin(min);
        return Node;
    }

    MaxMinNode Max_Min_Div(int a[], int start, int end) {
        int max, min, mid;
        MaxMinNode Node = new MaxMinNode();
        if (start == end) {
            Node.SetMax(a[start]);
            Node.SetMin(a[start]);
            return Node;
        } else {
            mid = (start + end) / 2;
            MaxMinNode Node1 = Max_Min_Div(a, start, mid);
            MaxMinNode Node2 = Max_Min_Div(a, mid + 1, end);
            if (Node1.GetMax() <= Node2.GetMax())
                max = Node2.GetMax();
            else
                max = Node1.GetMax();
            if (Node1.GetMin() <= Node2.GetMin())
                min = Node1.GetMin();
            else
                min = Node2.GetMin();
            return new MaxMinNode(max, min);
        }
    }
}

程序运行结果如下：

元素序列：
65 32 78 -16 90 55 26 -5 8 41
普通比较算法：Max=90, Min= -16
分治算法：Max=90, Min= -16

分治法求最大值和最小值（Java实现）

相关文章