我写了一个快速排序的程序，但是当我将数组的元素增加到10000的时候，程序就会溢出，如果用冒泡排序的话，程序不会溢出，而且用时也比快速排序短，快速排序到底该怎么用呢？

1. <div class="blockcode"><blockquote>/*
   
2.          * num：是要排序的数组
   
3.          * start：排序的开始位置
   
4.          * end：排序的结束位置
   
5.          */
   
6.         public static void quickSort(int num[],int start,int end){
   
7.                 //i用于从左向右遍历
   
8.                 int i=start;
   
9.                 //j用于从右向前左遍历
   
10.                 int j=end;
    
11.                 //用于保存基准元素
    
12.                 int tmp;
    
13.                
    
14.                 if(start<end){
    
15.                         //将第一个元素作为基准元素
    
16.                         tmp=num[start];
    
17.                         //从区间两端交替向中间扫描，直到i==j为止
    
18.                         while(i!=j){
    
19.                                 //从右向左扫描，找第一个小于基准元素的元素
    
20.                                 while(j>i&&num[j]>tmp){
    
21.                                         j--;
    
22.                                 }
    
23.                                 //找到这样的元素，就把它放到左区间去
    
24.                                 num[i]=num[j];
    
25.                                 //从左向右扫描，找第一个大于基准元素的元素
    
26.                                 while(i<j&&num[i]<tmp){
    
27.                                         i++;
    
28.                                 }
    
29.                                 //找到，把它放到右区间去
    
30.                                 num[j]=num[i];
    
31.                         }
    
32.                         //将基准元素放到合适位置
    
33.                         num[i]=tmp;
    
34.                         //对左区间递归排序
    
35.                         quickSort(num, start, i-1);
    
36.                         //对右区间递归排序
    
37.                         quickSort(num, i+1, end);
    
38.                 }

复制代码

看错了 ，编辑掉

哇呜，我也对这个挺感兴趣

我只知道快速排序是个不稳定（运算时间不稳定，有的时候一个很简单的问题可能却花了很长的时间）的排序算法，不适合用来小数据量的排序。

我对这个算法用得次数比较少，不好回答你，期待高手回答

快速排序出现栈溢出也很正常。。因为程序是递归调用而且一般来说堆栈大小是固定的，当数据量过大而且遇到最坏情况每次都分成1和n-1时就容易出现栈溢出。。。如果要避免栈溢出的话，可以尝试把快速排序写成非递归的。

//        快速排序
//        （1）基本思想：选择一个基准元素,通常选择第一个元素或者最后一个元素,通过一趟扫描，将待排序列分成两部分,一部分比基准元素小,一部分大于等于基准元素,此时基准元素在其排好序后的正确位置,然后再用同样的方法递归地排序划分的两部分。
//         
        public class quickSort {
               
        public static int getMiddle(int[] list, int low, int high) {      
                    int tmp = list[low];    //数组的第一个作为中轴      
                    while (low < high) {      
                        while (low < high && list[high] >= tmp) {      
            
              high--;      
                        }      
                        list[low] = list[high];   //比中轴小的记录移到低端      
                        while (low < high && list[low] <= tmp) {      
                            low++;      
                        }      
                        list[high] = list[low];   //比中轴大的记录移到高端      
                    }      
                   list[low] = tmp;              //中轴记录到尾      
                    return low;                   //返回中轴的位置      
                }  
       
        public static void _quickSort(int[] list, int low, int high) {      
                    if (low < high) {      
                       int middle = getMiddle(list, low, high);  //将list数组进行一分为二      
                        _quickSort(list, low, middle - 1);        //对低字表进行递归排序      
                       _quickSort(list, middle + 1, high);       //对高字表进行递归排序      
                    }      
                }  
       
       
        public static void main(String[] args) {
               
                int a[]={49,38,65,97,76,13,27,49,78,34,12,64,5,4,62,99,98,54,56,17,18,23,34,15,35,25,53,51};   
               
                if (a.length > 0) {    //查看数组是否为空      
                       
            _quickSort(a, 0, a.length - 1);     
            
         }  
               
                for(int i=0;i<a.length;i++)   
                       
                System.out.print(a[i]+"  ");
               
        }

       
        }   
          

我试了一下 应该没问题  

颜春 发表于 2013-2-27 22:07
//        快速排序
//        （1）基本思想：选择一个基准元素,通常选择第一个元素或者最后一个元素,通过一趟扫描，将 ...

你的算法和我的算法是一样的，也会导致栈溢出。我想把递归写成非递归，这样就不会导致栈溢出了，可是这东西我不会写，你看看你写成非递归好不好弄。

张晋瑜 发表于 2013-2-21 19:56
哇呜，我也对这个挺感兴趣

我只知道快速排序是个不稳定（运算时间不稳定，有的时候一个很简单的问题可能却 ...

不稳定的意思不是很简单的问题花了很长时间，排序方法分为稳定和不稳定，指的是假如有两个相同的数，排序后这两个数的前后位置和排序前不一样，那么这种排序就是不稳定的。而快速排序很简单的问题可能花了很长时间是因为快排的特点，越是无序的数快排越快。平均时间复杂度是O（nlog以2为底n的对数）。这个数据结构有详细解答。