算法概论实验二

算法概论实验

1 K路归并

教程1
教程2

1.0 问题描述

将$k$个已经排序的数组归并成一个大的排序的结果数组。

1.1 初步分析

其实这个问题可以说是一个问题的更加普遍形式。回顾一下我们在讨论归并排序的时候。那时候我们是将一个数组分解成两个子序列进行排序，然后再进行归并。这个过程一直递归下去。而其中归并结果的过程正好就是将两个已经排好序的序列合并成一个排好序的数组。我们可以看下面这一部分代码来回顾一下当时的实现：

private static void merge(int[] r, int low, int mid, int high) {
        // TODO  归并两个有序数组
        int k = 0;
        int i = low;
        int j = mid + 1;
        int[] tmp = new int[high - low + 1];
        while (i <= mid && j <= high) {
            if (r[i] <= r[j])
                tmp[k++] = r[i++];
            else
                tmp[k++] = r[j++];
        }
        while (i <= mid)
            tmp[k++] = r[i++];
        while (j <= high)
            tmp[k++] = r[j++];
        for (int m : tmp)
            r[low++] = m;
    }

$2$路合并的思路很简单，每次都比较位于两数组最前面的元素，取中间比较小的那个，一直到某序列结束，把另一个序列的元素放在后面即可。

1.2 思路

由题意，有$k$个排好序的数组，假设所有数组的元素总和为$n$。只要不停的遍历数组，模仿$2$路归并，从每个数组里面从头到尾的去取，然后把每次得到的最小的元素取出来就可以。这样，我们就很容易得到一个解决办法一。

1.21 方法一：循环遍历

这个办法的思路就比较直接，首先，我们比较所有k个数组的头一个元素，找到最小的那一个，然后取出来。我们在该最小元素所在的数组取下一个元素，然后重复前面的过程去找最小的那个。这样依次循环直到找到所有的元素。

public static void process(List<int[]> lists) {
        int min = Integer.MAX_VALUE;
        boolean notEmpty = true;
        int count = 0;
        int pos = -1;
        int[] flag = new int[lists.size()];// 记录K路的各路位置
        for (int[] r : lists)
            count += r.length;
        int[] res = new int[count];
        count = 0;//重置，后面用于结果计数
        while (notEmpty) {
            for (int i = 0; i < lists.size(); i++) {
                if (flag[i] < lists.get(i).length
                        && lists.get(i)[flag[i]] < min) {
                    min = lists.get(i)[flag[i]];
                    pos = i;// 最小值来源于第i路
                }
            }
            if (min != Integer.MAX_VALUE) {
                res[count++] = min;// 把最小值放到res中。
                flag[pos]++;//第K路下标后移
                min = Integer.MAX_VALUE;
            } else {
                notEmpty = false;
            }
        }
        System.out.println("K路合并之后" + " ");
        for (int arr : res)
            System.out.print(arr + " ");
    }

程序采用用一个$notEmpty$来标志所有序列是否已经遍历完了。我们每次遍历所有序列的当前元素，找到最小的。这样找一个最小元素都要比较$k$次，假设所有$n$个元素，其总体时间复杂度就达到了$O(nk)$。

1.22 方法二：最小堆k路归并排序

(1)用堆排序来合并
我们知道堆的排序效率是非常高的，我们考虑到用堆来实现，我们创建一个最小堆。首先把所有的$n$个数组的第一个元素放入最小堆中，这个最小堆的大小为$k$。这样我们调整堆结构，那么它的第一个元素就是

$$min( min(a_1),min(a_2)....min(a_n))$$ 显然就是所有数中的最小元素。

(2)找元素替补
在每一个数组中，元素都是按照升序排列的，当我们从堆中删除了一个最小的元素，就需要把他后面的一个元素重新入堆，因此，我们需要知道被删元素所在的数组，及其下一个元素的值
所以，如何去根据被删除的堆元素找这个被删除的堆元素所在的数组呢？这就需要在我们新建一个复合类型，它既包括当前的值，也包含这个当前值所在的数组的id,

(3)记录K个数组，目前元素的位置
随着程序的运行，没有参与排序的元素是越来越少的的，所以我们用一个长度为k的数组，这个数组用来记录所要排序的每个数组中还没参与排序的位置。它的值随着元素的选择后移。

(4)当某个数组移动到最后时候，我们得从下一个数组中找元素来填充

>(5)最后总有所有的数组位置都到了末端，这时候我们就要判断当前的堆是否为空，如果不为空，那么他们就包含了最后的几个元素了，我们依次把这些数按照最小顺序输出。如果当前的堆已经为空，那么直接跳出循环。

附录：

源码1：循环实现K路归并

import java.util.ArrayList;
import java.util.List;
public class test {
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int[] array1 = { 4, 5, 7, 8, 66, 69, 72, 79 };
        int[] array2 = { 3, 9, 42, 52, 53, 79, 82, 87 };
        int[] array3 = { 1, 17, 21, 31, 47, 55, 67, 95 };
        int[] array4 = { 6, 28, 49, 55, 68, 75, 83, 94 };
        int[] array5 = { 6, 28, 49, 55, 68, 75, 83, 94 };
        System.out.println("数组1为：");
        printarr(array1);
        System.out.println();
        System.out.println("数组2为：");
        printarr(array2);
        System.out.println();
        System.out.println("数组3为：");
        printarr(array3);
        System.out.println();
        System.out.println("数组4为：");
        printarr(array4);
        System.out.println();
        System.out.println("数组5为：");
        printarr(array5);
        System.out.println();
        List<int[]> arrayLists = new ArrayList<int[]>(4);
        arrayLists.add(0, array1);
        arrayLists.add(1, array2);
        arrayLists.add(2, array3);
        arrayLists.add(3, array4);
        arrayLists.add(4, array5);
        process(arrayLists);
    }
    public static void printarr(int []r)
    {
        for(int i:r)
            System.out.print(i + " ");
    }
    public static void process(List<int[]> lists) {
        int min = Integer.MAX_VALUE;
        boolean notEmpty = true;
        int count = 0;
        int pos = -1;
        int[] flag = new int[lists.size()];// 记录K路的各路位置
        for (int[] r : lists)
            count += r.length;
        int[] res = new int[count];
        count = 0;//重置，后面用于结果计数
        while (notEmpty) {
            for (int i = 0; i < lists.size(); i++) {
                if (flag[i] < lists.get(i).length
                        && lists.get(i)[flag[i]] < min) {
                    min = lists.get(i)[flag[i]];
                    pos = i;// 最小值来源于第i路
                }
            }
            if (min != Integer.MAX_VALUE) {
                res[count++] = min;// 把最小值放到res中。
                flag[pos]++;//第K路下标后移
                min = Integer.MAX_VALUE;
            } else {
                notEmpty = false;
            }
        }
        System.out.println("K路合并之后" + " ");
        for (int arr : res)
            System.out.print(arr + " ");
    }
}

2.

Split操作的要求是：以一个数组s和一个值v为输入，将数组s划分成3个子集：比v小的元素组成的集合，等于v的元素组成的集合以及比v大的元素组成的集合。设计和实现一种O(n)的就地split算法，即该算法不额外分配新的内存。