时间戳

首页 > 解决方案 > 我不明白为什么它会为快速排序程序提供数组越界异常？

java - 我不明白为什么它会为快速排序程序提供数组越界异常？

问题描述

我的代码似乎很好，但为什么它给出数组越界异常

    import java.util.*;  
    import java.io.*;  
    class Qsort  
    {  
        static int partition(int a[],int l,int h)  
        {   
            int pivot=l;  
            int u=h;  
            while(l<=h)  
            {
                while(a[pivot]>=a[l] && l<=u )  
                    l++;  
                while(a[pivot]<a[h])  
                    h--;  
                if(l<=h)  
                {   
                    int temp=a[l];  
                    a[l]=a[h];  
                    a[h]=a[l];      
                }  
            }  
            int t=a[pivot];  
            a[pivot]=a[h];  
            a[h]=t;  
            return h;     
        }  
        static void qs(int a[],int l,int h)  
        {  
            if(l<h)  
            {  
                int v=partition(a,l,h);  
                qs(a,l,v-1);  
                qs(a,v+1,h);  
            }  
        }  
    }  
    class Qsmain  
    {  
        public static void main (String ars[]) throws IOException  
        {  
            int a[]= {10, 7, 8, 9, 1, 5};  
            int n=6;  
            Qsort.qs(a,0,n-1);  
            System.out.println("The Sorted array is - ");  
            for(int i=0;i<n;i++)  
                System.out.print(a[i]+" ");   
        }  
    }

如图所示的异常：

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 6 out of bounds for length 6  
        at Qsort.partition(Qsmain.java:16)  
        at Qsort.qs(Qsmain.java:36)  
        at Qsmain.main(Qsmain.java:61)

标签： javaquicksort

解决方案

错误来自这一行：

    while(a[pivot]>=a[l] && l<=u )
        l++;

当您循环遍历时，在某个阶段l = 5and u = 5， so l++ = 6，然后抛出 Exception as a[6]is out of bounds （最后一个成员是a[5]）。因此，要解决此问题，请将语句更改为：

    while(a[pivot]>=a[l] && l<u ) //instead of l<=u, write l<u

但这将导致下一个错误，因为 while(l<=h)将转换为while(5<=5)然后将永远运行，因为最后一个值为l5 并且它不会增加。我会把它留给你来弄清楚如何解决这个问题。

推荐阅读