同样是调用递归算法，快速排序文件过大时栈溢出，而归并排序则不会，怎么解决

不知道你在哪里看到的快速排序，虽然写得这么纠结，但是结果还是对的。快速排序跟归并排序的最大区别是归并排序需要额外的空间，这个空间你是在堆里分配的，而快速递归不需要申请一个O(n)空间是因为通过函数栈保存了一些中间数据，正常来说当你元素很多时比如大于1M，函数栈肯定会溢出的，因为函数栈一般默认大小就是1M，函数栈大小是可以设置的，怎么设置函数栈大小你可以查百度。这些或许你都知道，不过你的递归算法也有点问题，因为你中间元素key就取了第一个元素，这会使得出现很多的递归浪费大量的栈空间，比如元素本来就有序的以你的算法时间复杂度为T(n) = T(n-1) + n，这个时间复杂度是O（nn），递归次数为n，正常情况递归次数应该是log（n）次的，你递归了时间不说栈空间就需要很大，所以这也可能是你栈溢出的一个可能。快速排序的中间元素key不能去第一个元素就行了，即使随机取一个都比你取第一个好多了。这里有我之前写的一个快速排序

struct my_traits<T>

{

typedef T value_type;

}

template<class BidirectIterator>

void IterSwap(BidirectIterator i,BidirectIterator j)

{

if(i == j) return;

typename my_traits<BidirectIterator>::value_type temp = i;

i = j;

j = temp;

}

template<class T>

void InsertSort(T first,T last)

{

for(T i = first + 1;i < last;++i)

{

T value = i;

T j = 0;

for(j = i;j - 1 >= first&&(j - 1) > value;--j)

j = (j - 1);

j = value;

}

}

template<class T>

T Median3(Tfirst,Tlast)

{

T middle = first + (last - first) / 2;

last--;

if(first > middle)

IterSwap(first,middle);

if(first > last)

return first;

if(middle < last)

return middle;

return last;

}

template<class T>

T Partition(T first,T last,T pivot)

{

while(true)

{

while(first < pivot) ++first;

--last;

while(last > pivot) --last;

if(first > last) return first;

IterSwap(first,last);

++first;

}

}

template<class T>

void QuikSort(T first,T last)

{

if(last - first >= 4)

{

T cut = Partition(first,last,Median3(first,last));

QuikSort(first,cut);

QuikSort(cut,last);

}

else

{

InsertSort(first,last);

}

}

一般每个进程的栈空间是限定的。（为什么限定？去学汇编和 *** 作系统就知道）

什么占用栈空间？

除去系统栈占用外，基本就是栈变量。（什么是栈变量？无语￥%&……%￥%&）

简单来说上面那个a就是栈变量。

修改有两个办法：

一 改为堆变量：

int pa = malloc(sizeof(int)10001000);

然后可以将pa当数组用。（数组和指针在C里基本等同）

当然，不用了记得free pa。

二 修改系统限制

这个栈变量= 100010004 = 4M。（约等于）

如果这个函数不频繁调用，也不递归，一般还是可以接受。

可以修改 *** 作系统对进程栈空间的大小限制，稍微调大一些。

ulimit查看系统的限制。（nix系统命令。不是windows的）

当然方法二非常不值得推荐

30000个测试数据在我的环境（4GB RAM）是没有问题的，但50000肯定有问题。一是递归导致内存耗得太多，至于是不是会耗尽，要看实际情况（也许测试环境是小型机呢）；二是50000已经超过C语言的int型范围（-32768~32767），即使你用long型数表示数组下标也不行，因为数组下标只能是int型。

我用随机数方式对30000大小的数组赋值，然后用你的快速排序进行测试，运行没有问题。参考C源代码如下：

#include "stdioh"

#include "stdlibh"

#include "timeh"

#define MAX 30000

void kuai(int a,int p,int r)

{

int i = p-1;

int j = p;

if(p < r)

{

for(j = p;j < r;j++)

{

if(a[j] <= a[r])

{

i++;

if(i != j)

{

a[i] ^= a[j] ^= a[i] ^= a[j];

}

}

}

if(i+1 != r)

{

a[i+1] ^= a[r] ^= a[i+1] ^= a[r];

}

kuai(a,p,i);

kuai(a,i+2,r);

}

}

void main()

{

int i;

int a[MAX];

srand((unsigned)time(NULL));

for(i=0; i<MAX; i++)

{

a[i] = rand();

}

kuai(a, 0, MAX-1);

for(i=0; i<MAX; i++)

{

printf("%8d", a[i]);

}

printf("\n");

}

刚运行 QuickSort(array,0,arraylength-1);这句的时候，进入函数内部key=11, 然后根据判断条件要找到比key小的数字，但是你的数组为int[]array=new int[]{11,213,134,44,77,78,23,43};没有比11小的，所以循环会直接运行到最后，当退出循环的时候,i变成了8，但是你的数组只有8个元素，对应索引0-7，所以会出现数组越界的情况，楼主应该是编程新手吧，编程强调逻辑能力，要把很多条件综合考虑才可以，否则编写出来的程序会有很多bug。

内存溢出（out of memory）

是指程序在申请内存时，没有足够的内存空间供其使用。

内存泄漏（memory leak）

是指程序在申请内存后，无法释放已申请的内存空间，占用有用内存。

注：内存泄漏最终会导致内存溢出

简单理解，内存溢出就是要求分配的内存超出了系统所给的。内存泄漏是指向系统申请分配内存进行使用（new），但是用完后不归还（delete），导致占用有效内存。

内存泄漏可分为4类：

1常发性内存泄漏

引起内存泄漏的代码会被很多次执行，每次执行的时候都会导致内存泄漏

2偶发性内存泄漏

在某些特定的环境下执行引起内存泄漏的代码，才会引起内存泄漏

从以上两种内存泄漏的方式来看，测试环境和测试方法在程序生命周期的重要性是不可或缺的。

3一次性内存泄漏

代码只会执行一次，但总有一块内存发生泄漏，多见于构造类的时候，析构函数没有释放内存。

4隐式泄漏

程序运行过程中不断的分配内存，直到结束时才释放内存，但一般服务器程序会运行较长的时间，不及时释放也会导致内存耗尽以至于内存泄漏。

综上所述，一次性内存泄漏对用户的程序维护是没有什么实质性的伤害，但在实际生活中，我们还是尽可能要避免此类的事件发生。

内存越界

是指向系统申请一块内存后，使用时却超出申请范围。比如一些 *** 作内存的函数：sprintf、strcpy、strcat、vsprintf、memcpy、memset、memmove。当造成内存泄漏的代码运行时，所带来的错误是无法避免的，通常会造成

1破坏了堆中内存内存分配信息数据

2破坏了程序其他对象的内存空间

3破坏了空闲内存块

附：如果在之前你的程序运行一切正常，但因为你新增了几个类的成员变量或者修改了一部分代码（前提是保证你的这些修改是完全正确的）而导致程序发生错误，则因考虑是否是内存被破坏的原因了，重点排查内存是否越界。

缓冲区溢出（栈溢出）

程序为了临时存取数据的需要，一般会分配一些内存空间称为缓冲区。如果向缓冲区中写入缓冲区无法容纳的数据，机会造成缓冲区以外的存储单元被改写，称为缓冲区溢出。而栈溢出是缓冲区溢出的一种，原理也是相同的。分为上溢出和下溢出。其中，上溢出是指栈满而又向其增加新的数据，导致数据溢出；下溢出是指空栈而又进行删除 *** 作等，导致空间溢出。