java - 在 Java 中实现快速排序

Question

我是一名计算机科学专业的学生，​​我正在尝试学习 Java 中的快速排序。我实现了自己的版本，我确信它可能不是最好的实现，所以不要对我太苛刻，这是为了学习目的。为了学习，我想知道为什么我的 Quicksort 会给我以下错误，我似乎无法解决或理解。提前致谢!

Exception in thread "main" java.lang.StackOverflowError
at java.io.FileOutputStream.write(FileOutputStream.java:326)
at java.io.BufferedOutputStream.flushBuffer(BufferedOutputStream.java:82)
at java.io.BufferedOutputStream.flush(BufferedOutputStream.java:140)
at java.io.PrintStream.write(PrintStream.java:482)
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 myQuickSort.mySwapMethod(myQuickSort.java:116)
at myQuickSort.partition(myQuickSort.java:52)
at myQuickSort.myQuickSortMethod(myQuickSort.java:39)
at myQuickSort.myQuickSortMethod(myQuickSort.java:40)
at myQuickSort.myQuickSortMethod(myQuickSort.java:40)

我的 Java 快速排序实现:

        public class myQuickSort {

        private int[] array;

        public static void main(String[] args) {
            int[] array = new int[] {3,5,74,3,67,45,23,6,34,12,889,4,25,1,0,7,4};
            myQuickSort test = new myQuickSort(array);

            System.out.println("Before:");
            for(int i =0; i < array.length;i++) {
                System.out.print(array[i]+",");
            }
            System.out.println("\n");
            test.myQuickSortMethod(0, array.length -1);

            System.out.println("After:");
            for(int i =0; i < array.length;i++) {
                System.out.print(array[i]+",");
            }

        }

        public myQuickSort(int[] array) {
            this.array = array;    
       }

        public void myQuickSortMethod(int indexStart, int indexEnd) {

            if(indexStart == indexEnd) {
                return;
            }

            int whereToSplit = partition(indexStart,indexEnd);
            myQuickSortMethod(indexStart, whereToSplit-1);
            myQuickSortMethod(whereToSplit+1,indexEnd);

        }

        private int partition(int indexStart, int indexEnd) {

            int leftOfPivotIndex = indexStart; //left pointer
            int rightOfPivotIndex = indexEnd;  //right pointer
            int pivotIndex =indexStart+(indexEnd-indexStart)/2; //pivot chosen from the middle of the list

//swapping pivot with the first element of the array
            mySwapMethod(indexStart,pivotIndex);

            pivotIndex = indexStart;
            if(indexStart != indexEnd) {
            leftOfPivotIndex++;
            }

        while(leftOfPivotIndex <= rightOfPivotIndex) {
                //left - pointer
                while(array[leftOfPivotIndex] < array[pivotIndex] && leftOfPivotIndex < rightOfPivotIndex ) {
                    leftOfPivotIndex++;
                }
                //right-pointer loop
                while(array[rightOfPivotIndex] >= array[pivotIndex] && leftOfPivotIndex < rightOfPivotIndex ) { 
                    rightOfPivotIndex--;  
                }

                mySwapMethod(leftOfPivotIndex,rightOfPivotIndex);

                if(leftOfPivotIndex == rightOfPivotIndex) {
                    System.out.println("BREAKING CASE");
                    if(array[leftOfPivotIndex] <= array[pivotIndex]) {
                        mySwapMethod(pivotIndex,leftOfPivotIndex);
                        return leftOfPivotIndex;
                    }else {
                        mySwapMethod(pivotIndex,leftOfPivotIndex -1);
                        return leftOfPivotIndex -1;
                    }

                }else {
                   //Move both left and write pointers after the swap
                    leftOfPivotIndex++;
                    rightOfPivotIndex--;   
                }
                if(leftOfPivotIndex == rightOfPivotIndex || leftOfPivotIndex > rightOfPivotIndex) {
                    System.out.println("BREAKING CASE");
                    if(array[leftOfPivotIndex] < array[pivotIndex]) {
                        mySwapMethod(pivotIndex,leftOfPivotIndex);
                        return leftOfPivotIndex;
                    }else {
                        mySwapMethod(pivotIndex,leftOfPivotIndex -1);
                        return leftOfPivotIndex -1;
                    }
                }       
          }
        return -1;      
        }

        private void mySwapMethod(int leftIndex,int rightIndex) {
            int temp = array[leftIndex];
            array[leftIndex] = array[rightIndex];
            array[rightIndex] = temp;       
        }
    }

Answer 1

当前输出为:

Before:
3,5,74,3,67,45,23,6,34,12,889,4,25,1,0,7,4,

BREAKING CASE
BREAKING CASE
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: -1
    at com.algorithm.sorting.myQuickSort.mySwapMethod(myQuickSort.java:98)
    at com.algorithm.sorting.myQuickSort.partition(myQuickSort.java:48)

原因是您没有将索引管理为

我会建议您使用任何 IDE 并调试您自己的代码 https://www.jetbrains.com/help/idea/debugging-your-first-java-application.html