黑马程序员技术交流社区

标题: 如题：快速排序时，被排序的数组个数为1000时没问题，但是个数为9999甚至更多时报错？ [打印本页]

---

作者: 徐青松    时间: 2014-2-19 13:30
标题: 如题：快速排序时，被排序的数组个数为1000时没问题，但是个数为9999甚至更多时报错？
public class QuickSortTest {
        public static void main(String args[])
        {
//这里大小是1000时没错，但是为9999时有错。下面数据也改过相应大小了的
                int[] aa=new int[1000];//int[] aa=new int[9999];时报堆栈溢出错误
                for (int i = 0; i <1000; i++) {//改为：for (int i = 0; i <9999; i++)相应大小
                        int aaa=i;
                        System.out.println(aaa);
                        aa[i]=aaa;
                }
                long startT=System.currentTimeMillis();
                quickSort(aa, 0, 999);//大小是9999时改为 quickSort(aa, 0, 9998)
                long endT=System.currentTimeMillis();
                System.out.println("系统运行时间："+(endT-startT));
        }
public static void quickSort(int[] strDate,int left, int right) {
                if (left >= right )
                        return ;
                int i = left, j = right;
                int temp,key;
                key = strDate[left];
       
                while (i !=j) {
                        while (strDate[j]>key&& i < j)
                                j--;
                        while (strDate[i]<key && i < j)
                                i++;
                       
                        temp = strDate[j];
                        strDate[j] = strDate[i];
                        strDate[i] = temp;
                }       
                i++;
                quickSort(strDate,left, i-1);
                quickSort(strDate,i , right);               
}
}
注意，其他排序方法我也是用同一数组，改了大小不会有错，为什么就是快速排序这里会出错。求解

---

作者: Amorvos    时间: 2014-2-19 14:46
9999的时候你用递归。。。你这不是疯了吗，内存耗尽当然报错，你这是生生的把内存用光，建议你用快速排序的非递归算法，给你个链接你自己看吧http://www.douban.com/note/234724751/

---

作者: flying    时间: 2014-2-19 18:17


程序没有错

1. public class Test2 {
   
2.     public static void main(String args[])
   
3.     {
   
4.             //这里大小是1000时没错，但是为9999时有错。下面数据也改过相应大小了的
   
5.             int[] aa=new int[9999];//int[] aa=new int[9999];时报堆栈溢出错误
   
6.             for (int i = 0; i <aa.length; i++) {//改为：for (int i = 0; i <9999; i++)相应大小
   
7.                     int aaa=i;
   
8.                     //System.out.println(aaa);
   
9.                     aa[i]=aaa;
   
10.             }
    
11.             long startT=System.currentTimeMillis();
    
12.             quickSort(aa, 0, aa.length-1);//大小是9999时改为 quickSort(aa, 0, 9998)
    
13.             long endT=System.currentTimeMillis();
    
14.             for (int i = 0; i < aa.length; i++) {
    
15.                                 System.out.print(aa[i]+"  ");
    
16.                                 if((i+1)%100==0)
    
17.                                         System.out.println();
    
18.                         }
    
19.             System.out.println("系统运行时间："+(endT-startT));
    
20.     }
    
21.         public static void quickSort(int[] strDate,int left, int right) {
    
22.             if (left >= right )
    
23.                     return ;
    
24.             int i = left, j = right;
    
25.             int temp,key;
    
26.             key = strDate[left];
    
27.    
    
28.             while (i !=j) {
    
29.                     while (strDate[j]>key&& i < j)
    
30.                             j--;
    
31.                     while (strDate[i]<key && i < j)
    
32.                             i++;
    
33.                     
    
34.                     temp = strDate[j];
    
35.                     strDate[j] = strDate[i];
    
36.                     strDate[i] = temp;
    
37.             }        
    
38.             i++;
    
39.             quickSort(strDate,left, i-1);
    
40.             quickSort(strDate,i , right);               
    
41. }
    
42. }

复制代码

你可能是在更改数组大小的时候没有改完整  建议用到数组大小的时候用length方法 获得
如果不是这个原因那 报什么错误呢

---

作者: 徐青松    时间: 2014-2-20 14:05

flying 发表于 2014-2-19 18:17
程序没有错

你可能是在更改数组大小的时候没有改完整  建议用到数组大小的时候用length方法 获得

public static void main(String args[])
        {
                int[] aa=new int[999];//这里大小是1000时没错，但是为9999时有错。下面数据也改过相应大小了的
                int len=aa.length;
                for (int i = 0; i <len; i++) {
                        int aaa=i;
                        System.out.println(aaa);
                        aa=aaa;
                }        
                quickSort(aa, 0, len-1);
        }

public static void quickSort(int[] strDate,int left, int right) {
                if (left >= right )
                        return ;
                int i = left, j = right;
                int temp,key;
                key = strDate[left];
       
                while (i !=j) {
                        while (strDate[j]>key&& i < j)
                                j--;
                        while (strDate<key && i < j)
                                i++;
                       
                        temp = strDate[j];
                        strDate[j] = strDate;
                        strDate = temp;
                }       
            i++;
                quickSort(strDate,left, i-1);
                quickSort(strDate,i , right);               
        }
改成你说的length来的也是会报错呢。Exception in thread "main" java.lang.StackOverflowError。我觉得是楼上说的把内存耗光问题吧

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2