Что на месте сортировать, когда два массива в порядке? - PullRequest
Новая
       14

Что на месте сортировать, когда два массива в порядке?

2 голосов
/ 13 января 2011

Я работаю над этим вопросом .Мой прототип функции: 

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

Во 2-й части функции я знаю, что leftPos to leftPos + (rightPos-leftPos) / 2 и (rightPos-leftPos) / 2 to rightPos отсортированы по порядку.

Я попытался подумать о том, как я мог бы сделать сортировку на месте, зная, что две части в порядке.Я не мог думать ни о чем.Я посмотрел на функцию слияния на сортировка слиянием , но она использует выходной массив, а не на месте.

Как мне отсортировать его на месте, зная, что оба среза расположены по порядку?

Примечание: я думал, что мог бы передать дополнительный массив такой же длины, что и основной массив, чтобы использовать его как временную память, но, как я думал, мне потребуется делать Array.Copy после каждого слияния.

1 Ответ

1 голос
/ 13 января 2011

Возможно слияние на месте, но оно сложное и не дает большого прироста производительности. Ниже приведен пример кода из здесь . 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);
}
...