归并排序的疑问？
#include "stdafx.h "
#include <iostream>
void Merge(int A[], int p, int q, int r)
{
int n1 = q - p + 1 ;
int n2 = r - q ;//不包括q,因此不加1
int* L = new int[n1+1];
int* R = new int[n2+1];
for(int i = 1; i <=n1; i++)
L[i] = A[p+i-1];
for(int j = 1; j <= n2; j++)
R[j] = A[q+j];
L[n1+1] = 2147483647;//整型的最大值，作为哨兵。
R[n2+1] = 2147483647;
i = 1;
j = 1;
for(int k = p; k <= r; k++)
if(L[i] <= R[j])
{
A[k] = L[i];
++i;
}
else
{
A[k] = R[j];
++j;
}
//delete [] L;
//delete [] R;
}
void Merge_Sort(int A[], int p,int r)
{
if(p < r)
{
int q = (p + r)/2;
Merge_Sort(A, p, q);
Merge_Sort(A, q+1, r);
Merge(A, p, q, r);
}
}
int main(int argc, char* argv[])
{
int A[9] = {2,3,4,5,1,3,4,6,9};
Merge_Sort(A, 0, 8);
int i = 0;
while( i < 9){
std::cout < <A[i] < <std::endl;
++i;
}
return 0;
}
请问一下：
这段代码没法delete,内存要泄露，这么办？
第二：每次递归调用的时候，都要分配内存，还是一次性分配内存？盼指教？
[解决办法]
//给你一个我的实现作参考
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <ctime>
using namespace std;
const int TOTAL_NUMBER = 20;
//两路归并排序
template <typename T>
void merage(T * a, int al, int am, int ar)
{
T * b = new T[ar - al +1];
int i = al, j = am + 1;
for(int k=0; k < ar - al + 1; ++k)
{
if(i > am) { b[k] = a[j++]; continue; }
if(j > ar) { b[k] = a[i++]; continue; }
b[k] = (a[i] < a[j]) ? a[i++]: a[j++];
}
for(int m=0; m < ar - al + 1; ++m)
a[m+al] = b[m];
delete [] b;
}
//归并排序算法
template <typename T>
void mergesort(T *R, int L, int H)
{
int M;
if(L < H)
{
M = (H + L)/2 ;
mergesort(R, L, M);
mergesort(R, M+1, H);
merage <T> (R, L, M, H);
}
}
void main()
{
clock_t start, finish;
srand((unsigned)time(NULL)); //以时间作随机数生成的种子
int *pa = new int[TOTAL_NUMBER+1];
for(int i=0; i <= TOTAL_NUMBER; i++ )
{
pa[i] = rand()%1000;
}
copy( pa, pa + TOTAL_NUMBER,
ostream_iterator <int> (cout, " "));
start= clock();
mergesort <int> (pa, 0, TOTAL_NUMBER-1); //调用归并排序算法
finish=clock();
cout < <endl;
copy( pa, pa + TOTAL_NUMBER,
ostream_iterator <int> (cout, " "));
cout < < "\nthe cost of times: " < <finish-start < <endl;
delete [] pa;
}
[解决办法]
int* L = new int[n1+1];
L[n1+1] = 2147483647;//整型的最大值，作为哨兵。
既然要用到下标n1+1，就应该new int[n1+2]，否则delete出错
