V2EX = way to explore
V2EX 是一个关于分享和探索的地方
Sign Up Now
For Existing Member Sign In
• 请不要在回答技术问题时复制粘贴 AI 生成的内容
This topic created in 4185 days ago, the information mentioned may be changed or developed.
我在网上查了一下归并排序算法，都需要分配一个新的数组，下面是我考虑的代码（不分配新的数组），不知道这样是否可行，效率如何，希望得到指点。
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 Nov 17, 2014
逼格不够高
|
 |
2
SlientHunter OP @Jaylee 不懂啥意思
|
 |
3
nolouch Nov 17, 2014 via Android
你合并那段，本来O(N)解决的，你又来了次O(N*N)的插入排序，，，还不去直接插入排序了呢。
@SlientHunter |
 |
4
jiang42 Nov 17, 2014
有错误吧－。－
mergesort([1], 0, 0)应该会出bug |
|
5
jiang42 Nov 17, 2014
看错了，没问题
|
 |
6
heliumhgy Nov 18, 2014 via Android
并归排序本来就不是in place的
|
 |
7
msg7086 Nov 18, 2014
不肯给空间，就多花时间。
|
 |
8
xylophone21 Nov 18, 2014
这个接口定义看的很是醉人啊
|
Select Language