排序时，两个数组都是为了什么代替？

问题描述

我的工作在这个问题上。我的函数原型为

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

在功能我知道leftPos到leftPos +（rightPos-leftPos）/ 2和（rightPos-leftPos）/ 2至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?

注：我想我可以传递一个额外的数组的长度相同的主阵列作为临时存储器，但方式我认为是需要我每次合并后做Array.Copy使用

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.

推荐答案

在就地合并是可能的，但它的复杂，不给太多的性能提升。下面是一些示例code这里。 从是 leftPos ，到是 rightPos ，透视是（rightPos-leftPos）/ 2 和长度各为一半的长度。

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

这篇关于排序时，两个数组都是为了什么代替？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！