2

我正在研究这个问题。我的函数原型是

static void Sort(byte[] arr, int leftPos, int rightPos)

在函数的第二部分，我知道 leftPos 到 leftPos + (rightPos-leftPos)/2 和 (rightPos-leftPos)/2 到 rightPos 是按顺序排序的。

我试着思考如何在知道这两个部分是有序的情况下进行就地排序。我想不出任何。我查看了合并排序上的合并函数，但它使用输出数组而不是就地数组。

知道两个切片都是有序的，我如何对其进行排序？

注意：我在想我可以传入一个与主数组长度相同的额外数组以用作临时内存，但我想的方式需要我在每次合并后执行 Array.Copy。

4

1 回答 1

1

In-place merge is possible, but it's complicated and doesn't give much performance gain. Below is some sample code from here. from is your leftPos, to is your rightPos, pivot is your (rightPos-leftPos)/2 and the lengths are the lengths of each half.

void merge(int from, int pivot, int to, int len1, int len2) {
  if (len1 == 0 || len2==0) return;
  if (len1+len2 == 2) {
   if (compare(pivot, from) < 0)
    exchange(pivot, from);
   return;
  }
  int first_cut, second_cut;
  int len11, len22;
  if (len1 > len2) {
   len11=len1/2;
   first_cut = from + len11;
   second_cut = lower(pivot, to, first_cut);
   len22 = second_cut - pivot;
  } else {
   len22 = len2/2;
   second_cut = pivot + len22;
   first_cut = upper(from, pivot, second_cut);
   len11=first_cut - from;
  }
  rotate(first_cut, pivot, second_cut);
  int new_mid=first_cut+len22;
  merge(from, first_cut, new_mid, len11, len22);
  merge(new_mid, second_cut, to, len1 - len11, len2 - len22);
}
于 2011-01-12T23:12:31.020 回答