C++关于快速排序问题,我写的一个快速排序,测试时,当数组长度为1000时,还可以,可是到了1000000时就会出错

Question

//C++关于快速排序问题,我写的一个快速排序,测试时,当数组长度为1000时,还可以,可是到了1000000时
//就会出错,很想知道问题出在哪里?求教?,我在VS2013环境下测试的

#include<iostream>

#include<ctime>
using namespace std;


void QuickSort(int *a, int low, int high);
int FindPos(int *a, int low, int high);


int main()
{
clock_t begin, end;
begin = clock();
srand(time(0));


int l = 100000; //定义生成的多少数字

int *a = new int[l];
for (int i = 0; i < l; i++)
a[i] = rand(); //随机生成数


QuickSort(a, 0, l); 

end = clock();
cout << end - begin << " ms" << endl;
return 0;
}


void QuickSort(int *a, int low, int high)
{
if (low < high)
{
int pos = FindPos(a, low, high);
QuickSort(a, low,pos-1);
QuickSort(a,pos+1,high);
}
}
int FindPos(int *a, int low, int high)
{
int temp = a[low]; 
while (low < high) 
{
while (low < high&&a[low] <= temp) 
low++; 
a[high] = a[low]; 


while (low < high&&a[high] >= temp) 
high--; 
a[high] = a[low]; 
} 
a[low] = temp; //也可以  a[high]=temp
return low; //也可以是  return high;
}

Answer 1

我知道了. while (low < high&&a[high] >= temp) high--; a[high] = a[low]; 的最后一句应该改为 a[low]=a[high]... 谢谢你了...

Answer 2

没看，估计栈溢出

Answer 3

应该不是，用shell排序时 int可以达到目的，试过了，还是一样的结果

Answer 4

我知道了. while (low < high&&a[high] >= temp) high--; a[high] = a[low]; 的最后一句应该改为 a[low]=a[high]... 谢谢你了...

Answer 5

应该是int溢出了，可以尝试用long。甚至long long