数据结构，一道排序思考题求解

某群上有人问了一个排序问题。乍一看好像很简单，细想之后才发现非常难，甚至不一定有解。偶们几个人想了一天，没搞定，最后决定到这里来问。题目如下：

现有一个数组，长度为n，其前m个元素和后n-m个元素都已经排序过了。

现在求算法将整个数组排序，要求时间复杂度O(n)，空间复杂度O(1)。如果有解，请给出程序；如果无解，请证明。

================================================================

为了简化描述，避免处理细节，在此给出输入条件：

1 输入：一个int型数组、长度n 和前半部分长度m（不用自己扫描）。

2 数组已经排序的两部分都是递增的，且长度都不为0；排序后要求整个数组递增。

26 个解决方案

#1

时间复杂度为O(N)应该没问题吧,从一个数组里取一个元素出来与另一个若干元素来比较实现排序,看似复杂,其时间复杂度并未超出N的一次多项式.空间复杂度为O(1)的话,不明白什么意思.不过如果怕一个变量产生多个拷贝的话,用指针数组或许可以解决这个问题.

#2

应该是不行的.否则stl中的inplace_merge算法就用这个了.

#3

现有一个数组，长度为n，其前m个元素和后n-m个元素都已经排序过了。
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
说明这个数组本来就是排序过了，其实你什么都不需要做，属于有病的题目。

#4

补充一下，如果问题是：
现有一个数组，长度为n，其前m个元素和后k个元素都已经排序过了。求时间复杂度O(n)，空间复杂度O(1)的算法。

除非是特殊情况，否则不存在此通用算法。

#5

mark 一下

#6

up 一下

#7

#define n 10
#define m 4
char str[n] = {...};
char *p = &str[0];
char *q = &str[m];
char t;
int i;

t = *p;
for(i = 0; i < n; i++)
{
    if(*p < *q)
    {
        t = *q;
        p++;
    }
    else
    {
        t = *p;
        *p = *q;
        *q = t;
        q++;
    }
}

#8

回复人： ZhangYv(我被降级了，哭>_<) ( ) 信誉：100  2006-01-18 18:57:00  得分: 0

   现有一个数组，长度为n，其前m个元素和后n-m个元素都已经排序过了。
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
说明这个数组本来就是排序过了，其实你什么都不需要做，属于有病的题目。


＝＝＝＝＝＝＝＝＝＝＝
你想的太简单了，你怎么知道这两个数组里的数据都是严格递增的？
不过后来的补充倒还是不错

我想这个问题时间复杂度应该在N的一次幂的数量级内，空间复杂度只要交换指针位置就行，不必产生中间变量之类的额外消耗
其实这个问题可以改造成两个有序数列的合并问题，普通的算法就可以实现O（n）

#9

这就是并归排序，按数据结构书中说的最好时间是O(nlgn)辅助空间是O(n)
看来是实现不了你的期望了，但如果哪位能做到就太伟大了:)

#10

看了stl中的inplace_merge
它倒是在内存充足的情况下能实现线形时间，但怎样实现的呢?
哪位高手能给出时间O(n)空间不限的算法

#11

有意思。up

#12

两个有序表的一次归并排序算法
本来就是0（N）吧！
空间也是0（1）啊

//------------------------------------------------
这里其实就是两个顺序表！
因为第二个表的头一个元素位置已知

#13

用归并排序的思路
int a[N];//整个数组
int S1=0,S2=M;
int E1=0,E2=N;//两个有序表的首尾
int i=S1,j=S2;
int t;
while(i<S1 && j<S2)
{
  if(a[i]>a[j])
  {
     swap(a[i],a[j]);//大的放后面，此处就需要O(1)的空间
     i++;
     break;
  }
  if(a[i]<a[j])
  {
     j++;
     break;
   }
  i++;
  swap(a[i],a[j]);
}

这样循环次数最多就n次。时间O(n)。
空间仅需要一个用于交换的，O(1)

#14

这样循环次数最多就n次。时间O(n)。
空间仅需要一个用于交换的，O(1)
-----------------------------------------------
肯定不行，不信你试试

#15

这道题基本不可能找到楼主所说的那种复杂度的算法。前面几位提到的归并排序要么需要O(N)的数组来记录二分归并后的结果，要么需要O(N)的空间来模拟一个类似链表的操作。就我目前所看过的所有数据结构书上的算法，我看他们还不太可能已经解决了楼主的问题，肯定需要额外的存储空间的。

#16

这个不是华为的面试题么？
我看的答案：
void testpaixu()
{ int a[10]={3,6,8,4,2,9,7,1,5,10};
  int b,i;
  for(i=0;i<10;i++)
  {
  b=a[a[i]-1];
    a[a[i]-1]=a[i];
    a[i]=b;
  }
  for(i=0;i<10;i++)
  printf("%d ",a[i]);
}

#17

以前看到的答案，贴出来给大家一起分享。

#18

oosky2004(oosky) 的只适合严格递增，内容只能是（1--n）的

#19

oosky2004(oosky) 的不行。
因为oosky2004的题目中元素是1~10
这暗示可以从元素的值直接知道其位置。

恩，看来很可能是无解的了，不晓得有人可以证明么？

#20

证明已经有了:

结果是否定，方法是反证法，即没人能证明有解开的方法，就能说明没有方法:)

#21

//n,m
//没那么复杂吧？不就是二路归并算法么？

int nList[n], ans[n];
int i,j,k;
for(i=0,j=m,k=0; i<m&&j<n; k++)
{
if(nList[i]>nList[j])
{
ans[k] = nList[i];
i++;
}
else
{
ans[k] = nList[j];
j++;
}
}
if(i<m)
{
for(;i<m; i++,k++)
{
ans[k] = nList[i];
}
}
else
{
for(;j<n; j++,k++)
{
ans[k] = nList[j];
}
}
//ans为排序后结果
/如果算上ans空间，那应该是O(n),o(n)
http://www.ohyee.net

#22

O(n),o(n)？
你每看清题目还是没戴眼睛？

#23

100分买一个2路归并的算法

#24

补充一下，如果问题是：
现有一个数组，长度为n，其前m个元素和后k个元素都已经排序过了。求时间复杂度O(n)，空间复杂度O(1)的算法。

===============================

如果 m = k = 1，那么……

#25

to lzf_china(岁月如歌)
是在同一个数组原地排序，不是二路归并。

嗯，看来不得不承认 0000000009(韩雷)的诡辩了。。。
明天就结帖

#26

题目不清，有点像华为的作风。基本上猜题就让你累个半死，然后还以此来鄙视你的专业水平不行。嘿嘿。这种题目有N种可能性，既可能有解，也可能没解。他要说简单，就是二路归并嘛，找个数空余数组，两个指针，完事。他要说不简单，就非说这个题没解。怎么说都是对的，你拿他没撤。呵呵

#1

#2