объединение двух отсортированных половин без дополнительной памяти!

Question

задано целочисленный массив, из которого отсортированы первая и вторая половина.написать функцию для объединения двух частей, чтобы создать один отсортированный массив на месте (не используйте дополнительное пространство).один из подходов, например: // 1,3,6,8, -5, -2,3,8

int l = 0;
int u = size;
int mid = (l+u)/2;
int i;
for (i = 0; i < mid; i++) {
  for (j = mid; j < size; j++) {
    if (a[i] >= a[j]) {
      temp = a[j];
      for (i = mid-1; i >= 0; i--)
        a[i+1] = a[i];
      a[0] = temp;
    }
  }
}

, но я думаю, что для этого должен быть некоторый O (n) алгоритм1004 *

Answer 1

Действительно, существует O (n) алгоритмов для объединения на месте. Они обычно довольно сложны, хотя. Для нескольких идей, пожалуйста, смотрите статьи, такие как Хуан, Лэнгстон (PDF) или Катаджайнен, Пасанен, Теухола (PostScript) . Они на самом деле определяются на основе точных условий того, какой тип дополнительной памяти разрешен, без обмана с использованием стека рекурсии и т. Д.

Answer 2

Вы можете сделать это, пройдя массив один раз, от 0 до его последнего элемента.Вам просто нужно подумать о том, с чем вам нужно сравнить или поменять местами «текущий» элемент, и это станет довольно просто.

Вам придется сохранить несколько дополнительных переменных, чтобы отслеживать текущий элемент, и«другой» элемент, с которым вам нужно сравнить его.

Кроме того, вы можете рассмотреть основные стили форматирования кода C.Нет стиля, который делает всех на 100% счастливыми, но есть множество стилей, которые делают всех несчастными.

---- Отредактировано ----

Хорошо, это гораздо больше похоже напроблема «дразнилки», а не серьезная проблема информатики.Проблема в том, что «дополнительная память» очень плохо определена, и поэтому вы можете достичь результата, если вы помните, что рекурсия разрешена только в языке программирования, и что рекурсивный вызов требует дополнительного стека (который никто не собирается рассматривать выделение памяти так, как этого требует реализация языка программирования).

По сути, такой вопрос предназначен для того, чтобы увидеть, смотрите ли вы на проблему и видите ли рекурсивное решение.*

#include <stdio.h>

void sort(int index, int start1, int end1, int start2, int end2, int* array) {
  if (index >= end2) {
    return;
  }
  int lower;
  if (array[start1] <= array[start2]) {
    lower = array[start1];
    sort(index+1, start1+1, end1, start2, end2, array);
  } else {
    lower = array[start2];
    sort(index+1, start1, end1, start2+1, end2, array);
  }
  array[index]=lower;
}

int main(int argc, char** argv) {
  int a[] = {1,3,6,8,-5,-2,3,8};
  sort(0, 0, 3, 4, 7, a);
  int i;
  for (i = 0; i <= 7; i++) {
    printf("%d, ", a[i]);
  }
  printf("\n");
  return 0;
}

Это чит?Вам решать.Однако сортировка была выполнена на месте, и кэшированные числа были аккуратно спрятаны в локальном пространстве в стеке вызовов, где вы не можете их реально выделить / отменить.

Возможна дополнительная оптимизация, ноони являются улучшением основной идеи: используйте рекурсию и стек вызовов для кэширования информации.

Answer 3

Лучший ответ, который я нашел, предполагая, что вы не можете использовать какую-либо вспомогательную память, состоит в том, чтобы выполнить массивную сортировку массива, которая theta(n log n), несколько быстрее, чем ваша текущая схема сортировки вставок.

Answer 4

любой из следующих

void Merge(int array[N])
{
for(int i=N/2;i<N;i++){
    int j=i;
    while(array[j]<array[j-1]&& j>=1){
        int temp=array[j];
        array[j]=array[j-1];
        array[j-1]=temp;
        j--;
    }
}
}

void Merge2(int array[N])
{
for(int i=N/2;i<N;i++){
   int key=array[i];
   int j=i-1;
   while(array[j]>key&& j>=0){
           array[j+1]=array[j];
           j--;
   }
   array[j+1]=key;
}
}

Answer 5

Я снова смотрел на это, и вот ваши O (n-1) и память (n + 1):

/**
 * Created by deian on 2016-12-22.
 */
public class Merge {
    public static void swap(int[] a, int i1, int i2) {
        int t = a[i1];
        a[i1] = a[i2];
        a[i2] = t;
    }

    public static void merge(int[] a) {
        int i1 = 0;
        int i2 = a.length / 2;

        System.out.printf("    %s,      i(%d,%d)       \n",    Arrays.toString(a),    i1, i2   );
        for (int di = 0; di < a.length-1; di++) {
            int ni;
            int oi1=i1;
            int oi2=i2;
            // i1 and i2 - always point to the smallest known numbers
            if (a[i1] > a[i2]) {
                ni = i2;
                i2++;
                if (i2>=a.length) {
                    i2--;
                }
            } else {
                ni = i1;
                i1++;
                if (i1 >= i2) {
                    i1 = di;
                }
            }
            if (di == i1) {
                i1 = ni;
            }
            swap(a, di, ni);
            System.out.printf("#%d: %s, i(%d,%d)s(%d>%d)i(%d,%d) \n", di+1, Arrays.toString(a), oi1, oi2,ni, di, i1,i2);
        }
        System.out.printf("    %s\n", Arrays.toString(a));
    }

    public static void main(String[] args) {
//        int[] a = new int[]{1, 3, 6, 8, -5, -2, 3, 8};
//        int[] a = new int[]{1, 3, 6, 8, -5, 2, 3, 8};
        int[] a = new int[]{1, 5, 6, 8, -5, 2, 3, 4};
        merge(a);
    }
}