黑马程序员技术交流社区

标题: 快速排序 栈溢出问题 [打印本页]
作者: 赵喜平    时间: 2013-4-3 20:24
标题: 快速排序 栈溢出问题
本帖最后由 赵喜平 于 2013-4-3 22:16 编辑
  1. class Arr {
  2.         public static void main(String args[])
  3.         {
  4.                 int arr[] = { 5, 3, 8, 2, 0, 9, 1, 7 };//35208179,

  6.                 quick(arr, 0, (arr.length-1));

  8.                printArr(arr);
  9.                
  10.         }
  11.         
  12.         public static void quick(int arr[],int left,int right)
  13.         {
  14.                 /*
  15.                  * 快速排序是选择一个key值，首先和从最后一个元素从后向前比较，
  16.                  * 大于最后一个换位置，然后和第一个元素从前往后比较，小于第一个换位置，
  17.                  * 这样以此类推*/
  18.                 int temp = getStart(arr,left,right);                                                 //此处会标识有栈溢出，这么回事？？？？？？？？？？？？？
  19.                 quick(arr,left,temp);                                                                   //？？？？？？？？？？、、
  20.                 quick(arr, temp + 1,right);
  21.         }
  22.         public static int getStart(int arr[],int left,int right)
  23.         {
  24.                 int i = 0, j = 0, key = 0;
  25.                
  26.                 left = i;
  27.                 right = j;
  28.                
  29.                 key = left;
  30.                
  31.                 if(arr.length==0) return 0;
  32.                
  33.                 while(left < right)
  34.                 {
  35.                         while(arr[j] > arr[key])
  36.                         {
  37.                                 --j;
  38.                         }
  39.                         swap(arr,arr[j],arr[key]);
  40.                         
  41.                         while(arr[i] < arr[key])
  42.                         {
  43.                                 --j;
  44.                         }
  45.                         swap(arr,arr[i],arr[key]);
  46.                 }
  47.                
  48.                
  49.                 return left;
  50.         }
  51.         
  52.         public static void swap(int arr[],int i,int j)
  53.         {
  54.                         int temp = arr[i];
  55.                         arr[i] = arr[j];
  56.                         arr[j] = temp;
  57.         }

  59.         public static void printArr(int arr[]) {
  60.                 for (int i : arr)
  61.                 {
  62.                         System.out.print(i + " ");
  63.                 }
  64.                 System.out.println();
  65.         }
  66. }
复制代码
作者: 高新星    时间: 2013-4-3 21:40
下面是我的理解，
这里的18,19形成了无限循环了
下面的主要代码省略

  2.     public static void quick(int arr[],int left,int right)
  3.     {
  4.             /*
  5.              * 快速排序是选择一个key值，首先和从最后一个元素从后向前比较，
  6.              * 大于最后一个换位置，然后和第一个元素从前往后比较，小于第一个换位置，
  7.              * 这样以此类推*/
  8.             int temp = getStart(arr,left,right);                    //left==0,right==6
  9.             quick(arr,left,temp);                                                            //left==0,temp==0------getStart(arr,0,0)---  quick(arr,0,0)---getStart(arr,0,0） .........无限循环           
  10.             quick(arr, temp + 1,right);
  11.     }
  12.     public static int getStart(int arr[],int left,int right)
  13.     {
  14.             int i = 0, j = 0, key = 0;
  15.             
  16.             left = i;                                                                                        //left==0
  17.             right = j;                                       //right==0
  18.             
  19.             key = left;
  20.             
  21.             if(arr.length==0) return 0;
  22.             
  23.             while(left < right)                                                                                                                                //不执行
  24.             {
  25.                   
  26.             }
  27.             return left;                                                                                                                                                //left==0
  28.     }
  29.    
复制代码




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