A股上市公司传智教育(股票代码 003032)旗下技术交流社区北京昌平校区

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

© 黑马刘杰 中级黑马   /  2013-2-21 19:43  /  9032 人查看  /  6 人回复  /   1 人收藏 转载请遵从CC协议 禁止商业使用本文

本帖最后由 黑马刘杰 于 2013-2-21 19:49 编辑

我写了一个快速排序的程序,但是当我将数组的元素增加到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技术分 +1 收起 理由
Rancho_Gump + 1

查看全部评分

6 个回复

倒序浏览
本帖最后由 李挺 于 2013-2-21 20:04 编辑

看错了 ,编辑掉
回复 使用道具 举报
哇呜,我也对这个挺感兴趣

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

我对这个算法用得次数比较少,不好回答你,期待高手回答
回复 使用道具 举报
快速排序出现栈溢出也很正常。。因为程序是递归调用而且一般来说堆栈大小是固定的,当数据量过大而且遇到最坏情况每次都分成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的对数)。这个数据结构有详细解答。
回复 使用道具 举报
您需要登录后才可以回帖 登录 | 加入黑马