算法学习——减治

减治算法的一些经典算法，如两序列中位数、折半查找、二叉树查找、插入排序等。

减治

经典算法

两个序列的中位数

public static int SearchMid(int[] A, int[] B) {
    int s1 = 0, e1 = A.length - 1, s2 = 0, e2 = B.length - 1;// 两个序列的上下界
    int mid1, mid2;
    while (s1 < e1 && s2 < e2) {
        mid1 = (s1 + e1) / 2;// A的中位数下标
        mid2 = (s2 + e2) / 2;// B的中位数下标
        if (A[mid1] == B[mid2]) return A[mid1];// 第①种情况
        if (A[mid1] < B[mid2]) {// 第②种情况
            if ((s1 + e1) % 2 == 0) s1 = mid1;
            else s1 = mid1 + 1;// 保证两序列长度相等
            e2 = mid2;
        } else {// 第③种情况
            if ((s2 + e2) % 2 == 0) s2 = mid2;
            else s2 = mid2 + 1;
            e1 = mid1;
        }
    }
    if (A[s1] < B[s2]) return A[s1];
    else return B[s2];
}

折半查找

public static int BinSearch(int[] r, int key) {
    int low = 0, high = r.length - 1;
    int mid;
    while (low <= high) {
        mid = (low + high) / 2;
        if (key < r[mid]) high = mid - 1;
        else if (key > r[mid]) low = mid + 1;
        else return mid;
    }
    return -1;
}

二叉查找树

public static BinaryTree InsertBST(BinaryTree root, int data) {
    if (root == null) {
        root = new BinaryTree();
        root.setData(data);
        root.setLchild(null);
        root.setRchild(null);
        return root;
    }
    if (data <= root.getData()) {
        root.setLchild(InsertBST(root.getLchild(), data));
    } else {
        root.setRchild(InsertBST(root.getRchild(), data));
    }
    return root;
}

public static BinaryTree CreateBST(int[] A) {
    BinaryTree T = new BinaryTree();
    for (int i = 0; i < A.length; i++) {
        T = InsertBST(T, A[i]);
    }
    return T;
}

public static BinaryTree SearchBST(BinaryTree root, int key) {
    if (root == null) return null;
    else if (root.getData() == key) return root;
    else if (key < root.getData()) return SearchBST(root.getLchild(), key);
    else return SearchBST(root.getRchild(), key);
}

选择问题

public static int Partition(int[] r, int low, int high) {// 划分
    int i = low, j = high;
    while (i < j) {
        while (i < j && r[i] <= r[j]) j--;// 右侧扫描
        if (i < j) {// 将较小的元素交换到前面
            int temp = r[i];
            r[i] = r[j];
            r[j] = temp;
            i++;
        }
        while (i < j && r[i] <= r[j]) i++;// 左侧扫描
        if (i < j) {// 将较大元的元素交换到后面
            int temp = r[i];
            r[i] = r[j];
            r[j] = temp;
            j--;
        }
    }
    return i;// 返回枢轴位置
}

public static int SelectMinK(int[] r, int low, int high, int k) {// 在r[low]和r[high]之间寻找第k小的元素
    int pivot = Partition(r, low, high);// 划分得到枢轴位置
    if (pivot == k)// 查找成功
        return r[pivot];
    if (pivot > k)// 枢轴大于k，则说明第k小元素在枢轴左侧
        return SelectMinK(r, low, pivot - 1, k);
    else// 否则在右侧寻找
        return SelectMinK(r, pivot + 1, high, k);
}

插入排序

public static void InsertSort(int[] r) {
    int j;
    for (int i = 2; i <= r.length - 1; i++) {
        r[0] = r[i];
        for (j = i - 1; r[0] < r[j]; j--)
            r[j + 1] = r[j];
        r[j + 1] = r[0];
    }
}

堆排序

public static void SiftHeap(int[] r, int key) {
    int i = key, j = 2 * i + 1, temp;// i为待筛的结点，j为i的左孩子
    while (j < r.length) {// 筛选还没有进行到叶子
        if (j < r.length - 1 && r[j] < r[j + 1]) j++;// 比较i的左右孩子，j为较大者
        if (r[i] > r[j]) break;// 根结点已经大于左右孩子中的较大者
        else {// 根节点与较大者交换
            temp = r[i];
            r[i] = r[j];
            r[j] = temp;
            i = j;
            j = 2 * i + 1;// 被筛的结点位于原来j的位置
        }
    }
}

public static void Sort(int[] r) {
    int i, temp;
    for (i = (r.length - 1) / 2; i >= 0; i--) {// 初始建堆
        SiftHeap(r, i);
    }
    for (i = 1; i <= r.length - 1; i++) {// 循环执行移走堆顶元素及重新调整堆的操作
        temp = r[0];
        r[0] = r[r.length - i];
        r[r.length - i] = temp;
        SiftHeap(r, 0);
    }
}

淘汰赛冠军问题

public static char Game(char[] r) {
    int i = r.length;
    System.out.println(r);
    while (i > 1) {
        i = i / 2;
        for (int j = 0; j < i; j++)
            if (Comp(r[j + i], r[j]))// 分组比赛
                r[j] = r[j + i]; // 胜者填入r[j]
        for (int k = 0; k < i; k++) {
            System.out.print(r[k]);
        }
        System.out.println();
    }

    return r[0];
}

public static boolean Comp(char i, char j) {// 模拟比赛，若i胜则返回true
    return i > j;
}

假币问题

public static int Coin(int low, int high, int n) {
    int i, num1, num2, num3;// num1、2、3存储3组硬币的数量
    int add1 = 0, add2 = 0;// add1、2存储前两组硬币的重量
    if (n == 1) return low + 1;// 递归结束条件
    if (n % 3 == 0) num1 = num2 = n / 3;// 返回的是序号，下标加1
    else num1 = num2 = n / 3 + 1; // 前两组有n/3(向上取整)枚硬币
    num3 = n - num1 - num2;
    for (i = 0; i < num1; i++)
        add1 += a[low + i];
    for (i = num1; i < num1 + num2; i++)
        add2 += a[low + i];
    if (add1 < add2)// 在第一组查找，下标范围low ~ low+num1-1
        return Coin(low, low + num1 - 1, num1);
    else if (add1 > add2)// 在第二组查找，下标范围low+num1 ~ low+num1+num2-1
        return Coin(low + num1, low + num1 + num2 - 1, num2);
    else// 在第三组查找，下标范围low+num1+num2 ~ high
        return Coin(low + num1 + num2, high, num3);
}