这是一个创建于 3658 天前的主题，其中的信息可能已经有所发展或是发生改变。
我在网上查了一下归并排序算法，都需要分配一个新的数组，下面是我考虑的代码（不分配新的数组），不知道这样是否可行，效率如何，希望得到指点。
void mergsort(int v[], int left, int right){
int i, j, k, middle, temp;
if((right-left) < 2){
if(v[left] > v[right]){
temp = v[left];
v[left] = v[right];
v[right] = temp;
}
return;
}
middle = (left + right) / 2;
mergsort(v, left, middle);
mergsort(v, middle+1, right);
for(i=left, j=middle+1;j<=right;j++){
if(v[i] >= v[j]){
temp =v[j];
k = j;
while(k > i){
v[k] = v[k-1];
k--;
}
v[k]= temp;
i++;
}
}
}
void mergsort(int v[], int left, int right){
int i, j, k, middle, temp;
if((right-left) < 2){
if(v[left] > v[right]){
temp = v[left];
v[left] = v[right];
v[right] = temp;
}
return;
}
middle = (left + right) / 2;
mergsort(v, left, middle);
mergsort(v, middle+1, right);
for(i=left, j=middle+1;j<=right;j++){
if(v[i] >= v[j]){
temp =v[j];
k = j;
while(k > i){
v[k] = v[k-1];
k--;
}
v[k]= temp;
i++;
}
}
}
 |
1
Jaylee 2014-11-17 19:32:20 +08:00
逼格不够高
|
 |
2
SlientHunter OP @Jaylee 不懂啥意思
|
 |
3
nolouch 2014-11-17 20:39:58 +08:00 via Android
你合并那段，本来O(N)解决的，你又来了次O(N*N)的插入排序，，，还不去直接插入排序了呢。
@SlientHunter |
 |
4
jiang42 2014-11-17 20:41:24 +08:00
有错误吧－。－
mergesort([1], 0, 0)应该会出bug |
|
5
jiang42 2014-11-17 20:45:25 +08:00
看错了，没问题
|
 |
6
heliumhgy 2014-11-18 01:26:49 +08:00 via Android
并归排序本来就不是in place的
|
 |
7
msg7086 2014-11-18 08:10:22 +08:00
不肯给空间，就多花时间。
|
 |
8
xylophone21 2014-11-18 13:21:25 +08:00
这个接口定义看的很是醉人啊
|
Select Language