合并排序算法

设子数组A[0:k]和A[k+1:N-1]已排好序(0≤K≤
N-1)。试设计一个合并这2个子数组为排好序的数组A[0:N-1]的算法。要求算法在
最坏情况下所用的计算时间为O(N)，只用到O(1)的辅助空间。

20 个解决方案

#1

lz会快速排序不？？

#2

用快速排序，在第一趟就能搞定！

#3

#include <stdio.h>

#define maxsize 20
typedef struct
{
  int    key;
  char   data;
}redtype;
typedef struct
{
  redtype     r[maxsize+1];
  int         length;
}sqlist;
int initlist(sqlist &l)
{
  l.length=maxsize;
  int i,j;
  for(i=1;i<=l.length;i++)
     {
       printf("plest input the key of %d:",i);
       scanf("%d",&l.r[i].key);
       printf("\n");
     }
   return (1);
}
int partition(sqlist &l,int low,int high)
{
  int pivotkey;
  l.r[0]=l.r[low];
  pivotkey=l.r[low].key;
  while(low     {
      while(low=pivotkey) --high;
      l.r[low]=l.r[high];
      while(low      l.r[high]=l.r[low];
     }
     l.r[high]=l.r[0];
     return low;
}//partition
void qsort(sqlist &l,int low,int high)
{
  int pivotloc;
  if(low     {
pivotloc=partition(l,low,high);
qsort(l,low,pivotloc-1);
qsort(l,pivotloc+1,high);
     }
}//qsort
void main()
{
   int i,j;
   sqlist  L;
   initlist(L);
   qsort(L,1,L.length);
   for(i=1;i<=L.length;i++)
     {
      printf("%d->",L.r[i].key);
     }
   printf("\n");
}

#4

O(1)的辅助空间
意味着不可能用递归了
同时快速排序最坏情况下时间是O（n^2)

也利用不了2个子数组为排好序的数组这一特点

#5

给出的原始序列比较特殊（部分有序）
在第一趟就能搞定sort！

#6

如果用的是：严蔚敏的教材，参见p275页图：10.7

#7

明显不行
比如说4567 12345
low=0（下标，也就是4）
high=8 （下标，也就是5）
一趟后最后一个还是5

#8

O(1)的辅助空间是什么意思? 是不是说用到常数个辅助变量就行了?

#9

是的

#10

直接做比较并交换的操作。
需要比较min( k, N-k-2 )次，辅助空间1个，最纯粹的O(1)了。

#11

其实就是合并排序的最后一趟

#12

我网上搜了下, 好像合并(也有叫归并的)排序算法都用到了O(n)的辅助空间啊.

#13

y_pro 的一个辅助空间的算法怎搞的? 没看明白, 讲详细点嘛.

#14

哦，又看了看书，觉得是归并算法。
不过辅助空间是 o(n)

#15

这个相当于合并排序递归的最后一趟，2个子序列已经有序了。直接遍历2个子序列，比较大小后原地置换。由于已经有序，所以比较次数是min( k, N-k-2 )次。原始置换，需要用到1个辅助空间。
所以，算法运行时间是O(N)，辅助空间是O(1)。

#16

比较大小的时候要注意，传统的合并算法是使用额外的存储空间进行插入操作的，采取原地置换的方法时需要把交换过的那个元素重新比较过，否则存在破坏有序性的可能性，导致算法运行结果不正确。

#17

楼上的给出算法, 说的太笼统, 看了还没思路. 我也曾经想用简单的交换去作, 结果不是得到错误的结果, 就是用到了比O(n)高阶的时间复杂度, 不知道你的具体算法, 很难想像你是怎么做的?

#18

美丽的C++殿堂 QQ群17850616 欢迎您的加盟，让我们携手共创IT美好明天。
爱好C++，那你就来吧！！欢迎您的加入。期待您的才华

#19

TO: y_pro(魔魂)

这个相当于合并排序递归的最后一趟，2个子序列已经有序了。直接遍历2个子序列，比较大小后原地置换。由于已经有序，所以比较次数是min( k, N-k-2 )次,需要把交换过的那个元素重新比较过，

=============================================================================
正是因为:需要把交换过的那个元素重新比较过，时间复杂度已经超过O(N)了,已经变成O(N^2)了.

我的结论是:
时间复杂度为O(N)，空间复杂度是O(1) 是不可能的!
又要马儿不吃草（才给O(1)空间），又要马儿跑得快（O(N)啊）……

#20

因爲兩個都已經是拍過序的了那麽直接就往裏面插就好了啊　。。。。。。。

#1