如何实现K路合并排序? [英] How to implement a k-way merge sort?

问题描述

我需要实现一个对未排序的数组或整数进行k次合并排序的函数.

I need to implement a function which does a k-way merge sort on an unsorted array or integers.

该函数接受两个参数，一个整数K，它是排序的方式"，总是2的幂.第二个参数是要排序的整数数组，其长度也是2的幂

The function takes in two parameters, an integer K, which is the "way" of the sort and always a power of 2. The second parameter is the array of integers to be sorted, whose length is also a power of 2.

该函数将返回包含已排序元素的数组.到目前为止，我知道如何实现常规的合并排序.我将如何修改此代码，以实现K-way合并排序?(注意:此函数不会返回排序后的数组，我也需要帮助.它也不接受K，因为它是常规的合并排序)

The function is to return an array containing the sorted elements. So far, I know how to implement a regular merge sort. How would I modify this code so that it implements a K-way merge sort? (Note: this function doesn't return the sorted array, I need help with that as well. It also doesn't take in K, since its a regular merge sort)

下面的代码:

public class MergeSort {

  public static void main(String[] args) {

  }

  public static void mergeSort(int[] inputArray) {
    int size = inputArray.length;
    if (size < 2)
        return;
    int mid = size / 2;
    int leftSize = mid;
    int rightSize = size - mid;
    int[] left = new int[leftSize];
    int[] right = new int[rightSize];
    for (int i = 0; i < mid; i++) {
        left[i] = inputArray[i];

    }
    for (int i = mid; i < size; i++) {
        right[i - mid] = inputArray[i];
    }
    mergeSort(left);
    mergeSort(right);
    merge(left, right, inputArray);
  }

  public static void merge(int[] left, int[] right, int[] arr) {
    int leftSize = left.length;
    int rightSize = right.length;
    int i = 0, j = 0, k = 0;
    while (i < leftSize && j < rightSize) {
      if (left[i] <= right[j]) {
        arr[k] = left[i];
        i++;
        k++;
      } else {
        arr[k] = right[j];
        k++;
        j++;
      }
    }
    while (i < leftSize) {
      arr[k] = left[i];
      k++;
      i++;
    }
    while (j < leftSize) {
      arr[k] = right[j];
      k++;
      j++;
    }
  }
}

推荐答案

常规合并排序是双向排序.您比较数组的前半部分和后半部分的元素，并将其最小复制到输出数组.

Regular merge sort is two-way sorting. You compare elements from the first and the second halves of array and copy smallest to output array.

对于k方式排序，您将输入数组划分为K个部分.K个索引指向每个部分的第一个元素.要有效地选择最小的元素，请使用优先级队列(基于二进制堆)，并在每一步从堆顶部弹出最小的元素.弹出属于第m部分的元素时，请从同一部分(如果仍然存在)推入下一个元素

For k-way sorting you divide input array into K parts. K indexes point to the first elements of every part. To effectively choose the smallest of them, use priority queue (based on binary heap) and pop the smallest element from the heap top at every step. When you pop element belonging to the m-th part, push the next element from the same part (if it still exists)

让您拥有16的数组长度且k =4.
第一个递归级别对从索引0..3、4..7、8..11、12..15复制的数组调用4个mergesorts.
第二个递归级别获得长度为4的数组，并为1个元素的数组调用4个mergesorts.
第三个递归级别获得长度为1的数组，并立即返回(已对此类数组进行排序).
现在，在第二个递归级别上，您将4个单元素数组合并为一个排序的数组.
现在，在第一个递归级别上，您将4个四元素数组合并为一个排序后的数组长度16

Let you have array length 16 and k = 4.
The first recursion level calls 4 mergesorts for arrays copied from indexes 0..3, 4..7, 8..11, 12..15.
The second recursion level gets length 4 array and calls 4 mergesorts for 1-element arrays.
The third recursion level gets length 1 array and immediately returns (such array is sorted).
Now at the second recursion level you merge 4 one-element arrays into one sorted array.
Now at the first recursion level you merge 4 four-element arrays into one sorted array length 16

这篇关于如何实现K路合并排序?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！