合并两个排序的一半没有额外的内存！

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）的算法中的这个..

Answer 1

我在此再次寻找，这里是你的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); 
    } 
} 

Answer 2

你可以通过走一次阵列来做到这一点，从0到它的最后一个元素。你只需要考虑你需要比较什么，或者交换“当前”元素，它变得很容易。

您必须保留一些额外的变量来跟踪当前元素，以及需要将其与其他元素进行比较。

另外，您可能需要查看主要的C代码格式样式。没有任何风格让每个人都百分之百快乐，但有很多风格让每个人都不快乐。

---- ----编辑

好吧，这更像是比一个严重的计算机科学问题“脑筋急转弯”的问题。问题在于“额外内存”的定义很差，所以如果您只记得编程语言允许递归，那么您可以通过很多方法实现结果，而that a recursive call requires extra stack（没有人会将内存分配视为它是编程语言实现所要求的）。

基本上，这样的问题是要看你是否看问题，看到递归解决方案。

#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

确实有O（n）的算法，对于就地融合。虽然它们通常很复杂。对于少数想法，请参阅Huang, Langston (PDF)或Katajainen, Pasanen, Teuhola (PostScript)等论文。这些实际上是根据允许的额外内存的精确条件来定义的，而不用使用递归堆栈等作弊。

Answer 5

以下任何

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