当两个数组有序时，如何进行就地排序？

发布于 2024-10-11 09:58:09 字数 560 浏览 5 评论 0原文

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

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

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

知道两个切片都按顺序排列时，如何对其进行排序？

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

原文

I am working on this question. My function prototype is

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

In the 2nd part of the function i know leftPos to leftPos + (rightPos-leftPos)/2 and (rightPos-leftPos)/2 to rightPos are sorted in order.

I tried thinking of how i could do an in place sort knowing the two parts are in order. I couldnt think of any. I looked at the merge function on merge sort but it uses an output array rather than in place.

How do i sort it in place knowing both slices are in order?

Note: I was thinking i could pass in a extra array that is the same length as the main array to use as temp memory but the way i thought of would require me to do Array.Copy after each merge.

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

絕版丫頭 2024-10-18 09:58:09

就地合并是可能的，但它很复杂并且不会带来太多性能提升。下面是此处的一些示例代码。 from 是您的 leftPos，to 是您的 rightPos，pivot 是您的 (rightPos-leftPos)/2 长度是每一半的长度。

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);
}

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);
}

回复收藏 0 原文

~没有更多了~