如何在归并排序中找到低点和高点

Question

我对归并排序算法有了基本的了解。但出于某种原因，我无法理解低值和高值的来源。这是我为 Merge 使用的代码。

void practiceMerge(int a[], int low, int mid, int high)
{
    int b[10000];
    int i = low, j = mid + 1, k = 0;

    while (i <= mid && j <= high) {
        if (a[i] <= a[j])
            b[k++] = a[i++];
        else
            b[k++] = a[j++];
    }
    while (i <= mid)
    b[k++] = a[i++];

    while (j <= high)
        b[k++] = a[j++];

    k--;
    while (k >= 0) {
        a[low + k] = b[k];
        k--;
    }
}

Answer 1

让我通过评论您的代码来解释：

//Sort an array a from its index low to its index high by merging two
//subarrays of a that go from low to mid and mid to high.
void practiceMerge(int a[], int low, int mid, int high)
{
    int b[10000]; //Buffer
    int i = low; //starting index in first sub array
    int j = mid + 1; //starting index in second sub array
    int k = 0; //starting index in buffer

    //While you DO NOT go beyond the limit of the first subarray
    //nor the second
    while (i <= mid && j <= high) {
        if (a[i] <= a[j])
            //Put the value of the first subarray, and move 
            b[k++] = a[i++];
        else
            //Put the value of the first subarray, and move
            b[k++] = a[j++];
    }
    //Finish copying first subarray if not done yet
    while (i <= mid)
    b[k++] = a[i++];
    //Finish copying second subarray if not done yet
    while (j <= high)
        b[k++] = a[j++];

    //Copy buffer to array a
    k--;
    while (k >= 0) {
        a[low + k] = b[k];
        k--;
    }
}

基本上，低、中和高是您正在查看的数组 "a" 的边界。 "a" 可能更大。例如：

a =  3 2 1 5 6 7 0 1 
low = 0
mid = 2
high = 4

这里是对a的前半部分进行排序。

编辑：您的函数合并数组。主要归并排序功能，拆分数组。它将是：

void merge_sort(int a[], int lo, int hi) {
   if (low >= hi)
      return; //Nothing to sort
   int mid = (lo+hi)/2; //The guy between lo and hi.
   merge_sort(a,lo, mid); //sort the left
   merge_sort(a, mid, hi); //sort the right
   practiceMerge(a, lo, mid, hi); //This merges the array
}

要理解（不要只是复制粘贴！）这样想：merge_sort 排序数组的一块，而不是整个数组，只是 lo 和 hi 之间的位。为此，它先对一半进行排序，然后对另一半进行排序。然后它将结果合并到数组中。因此，在 merge_sort 内部，"hi" 和 "lo" 是根据参数计算的。现在，您，用户，可能想要从 0 到末尾，或从第 10 到第 99 个索引对数组进行排序。那是你的选择。这就是您传递给调用的参数。

void main() {
   //Bla bla bla
   merge_sort(songs, 89, 250); //Only sort some songs
}

把它想象成一个黑盒子。你用一些参数调用它，盒子就会做它的事情。因为盒子使用自己，所以它知道如何调用自己（即它知道如何计算低、高和中），但递归中的初始调用是您作为用户的责任。

P.S.: 感觉我说的不是很清楚...

如何在归并排序中找到低点和高点

How to find the low & high in Merge Sort

c++

algorithm

mergesort