这个快速排序代码有什么问题

Question

我花了几个小时查看这个快速排序代码。请帮我找出错误。它正在报告运行次错误。在代码中，我将第一个元素 a[l] 作为基准。

import java.util.*;
import java.lang.*;
import java.io.*;

class sorting
{
    public static int[] a = {7,2,6,4,3};
    public static void quickSort(int l, int h)
    {
        if(l<h)
        {
        int y=l+1;
        for(int g=l+1;g<h;g++)
        {
            if(a[g]<=a[l])
            {
                int t = a[g];
                a[g] = a[l];
                a[l] = t;
                y++;
            }
        }
        int k=a[l];
        a[l] = a[y-1];
        a[y-1] = k;
        quickSort(l,y);
        quickSort(y+1,h);
        }
    }
    public static void main (String[] args) throws java.lang.Exception
    {
        quickSort(0,5);
        for(int s=0;s<5;s++)
            System.out.print(a[s] + "");
    }
}

Answer 1

实在看不懂你的代码。根据您的代码，另一种解决方案是：

public class sorting
{
   public static int[] a = {7,2,6,4,3};
   public static void quickSort(int l, int h) {
       if(l>=h||l<0){
           return;
       }
       int curStandard = l;
       for(int i = h; i > l;i--){//for
           if((a[i]>=a[curStandard]&&i>curStandard)||
                (a[i]<=a[curStandard]&&i<curStandard)){
               ;
           }else{//swap
               int temp = a[i];
               a[i] = a[curStandard];
               a[curStandard] = temp;
               curStandard = i;
           }
       }//for
       quickSort(l,curStandard-1);
       quickSort(curStandard+1,h);
   }

   public static void main (String[] args) throws java.lang.Exception
  {
    quickSort(0,5);
    for(int s=0;s<5;s++)
        System.out.print(a[s] + "");
 }
}

基本思想是使用第一个元素将原始数组分成两个sub_array并对sub_array进行相同的操作。

Answer 2

Why/how 正在中断：

在您的代码中，当调用 quickSort(l,h) 时，值为 l=0 和 h=2。这些值使 if if(l<h) 语句为真，函数一次又一次地递归，实际递归 5,657 次。具有讽刺意味的是，然后你得到一个 WhosebugError。运行时间错误发生，我假设，因为你试图递归太深。

这是输出：

Exception in thread "main" java.lang.WhosebugError
    at java.io.PrintStream.write(PrintStream.java:480)
    at sun.nio.cs.StreamEncoder.writeBytes(StreamEncoder.java:221)
    at sun.nio.cs.StreamEncoder.implFlushBuffer(StreamEncoder.java:291)
    at sun.nio.cs.StreamEncoder.flushBuffer(StreamEncoder.java:104)
    at java.io.OutputStreamWriter.flushBuffer(OutputStreamWriter.java:185)
    at java.io.PrintStream.write(PrintStream.java:527)
    at java.io.PrintStream.print(PrintStream.java:669)
    at java.io.PrintStream.println(PrintStream.java:806)
    at sorting.quickSort(sorting.java:26)
    ... this error occurs 1024 times ...

你逻辑有问题

我确定您在代码中添加了以下行：

    a[l] = a[y-1];
    a[y-1] = k;
    System.out.println("l: "+l+" y: "+y); // I added this line.
    quickSort(l,y); // this is line 26 that the errors were mentioning
    quickSort(y+1,h);

我不确定 if 语句之外的所有其他交换是为了什么。

固定代码：

import java.util.*;
import java.lang.*;
import java.io.*;

class sorting
{
    public static int[] a = {7,2,6,4,3};
    public static void quickSort(int l, int h) {
        if(l<h) {
            for(int g=l+1; g<h; g++) {
                if(a[g]<=a[l]) {
                    int t = a[g];
                    a[g] = a[l];
                    a[l] = t;
                }
            }
            quickSort(++l,h);
        }
    }

    public static void main (String[] args) throws java.lang.Exception
    {
        // updated this area incase more numbers are added.
        quickSort(0,a.length);
        for(int s=0;s<a.length;s++)
            System.out.print(a[s] + "");
    }
}

这个快速排序代码有什么问题

What is wrong with this Quick Sort code

java

sorting

quicksort

Why/how 正在中断：

固定代码：