java - 大情况下的快速排序会导致 stackoverflow

Question

我正在开发一个学校项目，该项目必须有 3 个带 1 个指针的快速排序、3 个带 2 个指针和 2 个堆的快速排序。

到目前为止，我已经编写了快速排序和堆之一。我遇到的问题是快速排序在小情况下工作正常，但在较大情况下我会遇到堆栈溢出。

Nore:每个快速排序都有一个简单的情况，在这种情况下它应该运行插入排序。

为什么我会出现堆栈溢出？

    package prog3;

    import java.util.Random;

    public class ArraySorts {

        public static void QuickSort1(int[] a, int n) {

            QuickSort1(a, 0, n - 1);
        }

        private static void QuickSort1(int[] a, int start, int end) {
             if ((end - start+1) <= 20) {
                int num = (end + 1) - start;
                insertion(a, num);
            }
             else {
                // use first element as division between small and big

                Random rand = new Random();
                int pivotIndex = start + rand.nextInt(end - start);
                swap(a, pivotIndex, start);
                int pivot = a[start];



                int partitionBook = partitionBook(a, start, end, pivot);

                // recursively sort the smalls and then the bigs

                QuickSort1(a, start, partitionBook - 1);

                QuickSort1(a, partitionBook + 1, end);
            }
        }



        public static void QuickSort2(int[] a, int n) {
            // 2 ptr partition, random pivot, easiest case = 20
            int left = 0;
            int right = n - 1;

            QuickSort2(a, left, right);

        }

        public static void QuickSort2(int[] a, int left, int right) {

             if ((right - left + 1) <= 20) {
                int num = right - left + 1;
                insertion(a, num);
            } else {
                // int pivot = a[right];
                Random rand = new Random();
                int pivotIndex = left + rand.nextInt(right - left + 1);
                swap(a, pivotIndex, right);
                int pivot = a[right];

                int partition = partition(a, left, right, pivot);

                QuickSort2(a, 0, partition - 1);
                QuickSort2(a, partition + 1, right);
            }

        }

        public static void QuickSort3(int[] a, int n) {

            QuickSort3(a, 0, n - 1);
        }

        private static void QuickSort3(int[] a, int start, int end) {
             if ((end - start) <= 20) {
                int num = (end + 1) - start;
                insertion(a, num);
            }
             else {
                // use first element as division between small and big


                int pivot = a[start];



                int partitionBook = partitionBook(a, start, end, pivot);

                // recursively sort the smalls and then the bigs

                QuickSort3(a, start, partitionBook - 1);

                QuickSort3(a, partitionBook + 1, end);
            }
        }


        public static void QuickSort4(int[] a, int n) {
            // 2 ptr partition, random pivot, easiest case = 1
            int left = 0;
            int right = n - 1;

            QuickSort4(a, left, right);

        }

        public static void QuickSort4(int[] a, int left, int right) {
            if ((right - left + 1) <= 1) {
                return;
            }
            // int pivot = a[right];
            Random rand = new Random();
            int pivotIndex = left + rand.nextInt(right - left + 1);
            swap(a, pivotIndex, right);
            int pivot = a[right];
            // System.out.println("Pivot: " + pivot);

            int partition = partition(a, left, right, pivot);

            QuickSort4(a, 0, partition - 1);
            QuickSort4(a, partition + 1, right);
        }

        public static void QuickSort5(int[] a, int n) {
            // 2 ptr partition, random pivot, easiest case = 500
            int left = 0;
            int right = n - 1;

            QuickSort5(a, left, right);

        }

        public static void QuickSort5(int[] a, int left, int right) {
            if ((right - left + 1) <= 500) {
                int num = right - left + 1;
                insertion(a, num);
            } else {
                // int pivot = a[right];
                Random rand = new Random();
                int pivotIndex = left + rand.nextInt(right - left + 1);
                swap(a, pivotIndex, right);
                int pivot = a[right];

                int partition = partition(a, left, right, pivot);

                QuickSort5(a, 0, partition - 1);
                QuickSort5(a, partition + 1, right);
            }
        }

        public static void QuickSort6(int[] a, int n) {

            QuickSort6(a, 0, n - 1);
        }

        private static void QuickSort6(int[] a, int start, int end) {
             if ((end - start+1) <= 1) {
                return;
            }
             else {
                // use first element as division between small and big

                Random rand = new Random();
                int pivotIndex = start + rand.nextInt(end - start);
                swap(a, pivotIndex, start);
                int pivot = a[start];



                int partitionBook = partitionBook(a, start, end, pivot);

                // recursively sort the smalls and then the bigs

                QuickSort1(a, start, partitionBook - 1);

                QuickSort1(a, partitionBook + 1, end);
            }
        }


        private static int partition(int[] a, int left, int right, int pivot) {
            int leftCursor = left - 1;
            int rightCursor = right;
            while (leftCursor < rightCursor) {
                while (a[++leftCursor] < pivot)
                    ;
                while (rightCursor > 0 && a[--rightCursor] > pivot)
                    ;
                if (leftCursor > rightCursor) {
                    break;
                } else {
                    swap(a, leftCursor, rightCursor);
                }
            }
            swap(a, leftCursor, right);
            return leftCursor;

        }
        private static int partitionBook(int[] a, int start, int end, int pivot) {
            // the index of the last small element

                        int lastSmall = start;

                        for (int unknown = start + 1; unknown <= end; unknown++) {
                            // see if the current element is small

                            if (a[unknown] < pivot) {
                                // and if so, put it with the other smalls

                                lastSmall++;

                                int temp = a[lastSmall];
                                a[lastSmall] = a[unknown];
                                a[unknown] = temp;
                            }
                        }

                        // put the pivot between the smalls and the bigs

                        int temp = a[start];
                        a[start] = a[lastSmall];
                        a[lastSmall] = temp;
                        return lastSmall;
        }

        public static void swap(int[] a, int left, int right) {
            int temp = a[left];
            a[left] = a[right];
            a[right] = temp;
        }

        public static void printArray(int[] a) {
            for (int i : a) {
                System.out.print(i + " ");
            }
        }

        public static int[] getArray() {
            int size = 10;
            int[] array = new int[size];
            int item = 0;
            for (int i = 0; i < size; i++) {
                item = (int) (Math.random() * 100);
                array[i] = item;
            }
            return array;
        }

        /**
         * Will return the left child's index
         * 
         * @param iIndex
         *            The index of the current position (Parent)
         * @return The index of the left child
         */
        static int Left(int iIndex) {
            return ((iIndex << 1) + 1);
        }

        /**
         * Will return the right child's index
         * 
         * @param iIndex
         *            The index of the current position (Parent)
         * @return The index of the right child
         */
        static int Right(int iIndex) {
            return ((iIndex << 1) + 2);
        }

        /**
         * Will return the parent of the current index
         * 
         * @param iIndex
         *            The index of the current position (Child)
         * @return The index of the parent
         */
        int Parent(int iIndex) {
            return ((iIndex - 1) >> 1);
        }

        /**
         * Swaps the values of the two index locations
         * 
         * @param firstIndex
         *            the index of the first number to exchange.
         * @param secondIndex
         *            The index of the second number to exchange.
         * @param ipHeap
         */
        static void Swap(int firstIndex, int secondIndex, int[] ipHeap) {
            int iTemp = ipHeap[firstIndex];
            ipHeap[firstIndex] = ipHeap[secondIndex];
            ipHeap[secondIndex] = iTemp;
        }

        /**
         * Determines if there needs to have a swap of a child and parent. It will
         * determine which child needs to be swapped.
         * 
         * @param parent
         *            index of the parent (current index)
         * @param ipHeap
         *            The array that needs the operations performed.
         * @param iSize
         *            The adjusted size of the array
         * @return The index of the largest value.
         */
        static int SwapWithChild(int parent, int[] ipHeap, int iSize) {
            int leftChild = Left(parent);
            int rightChild = Right(parent);
            int iLargest = parent;
            if (rightChild < iSize) {
                if (ipHeap[leftChild] < ipHeap[rightChild]) {
                    iLargest = rightChild;
                } else {
                    iLargest = leftChild;
                }
                if (ipHeap[parent] > ipHeap[iLargest]) {
                    iLargest = parent;
                }
            } else if (leftChild < iSize) {
                if (ipHeap[parent] < ipHeap[leftChild]) {
                    iLargest = leftChild;
                }
            }
            if (ipHeap[parent] < ipHeap[iLargest]) {
                Swap(parent, iLargest, ipHeap);
            }
            return iLargest;
        }

        /**
         * Replaces the value of the root with the value of the last element of the
         * heap.
         * 
         * @param ipHeap
         *            The heap to have the root replaced.
         * @param iSize
         *            The size of the heap.
         */
        void RemoveRoot(int[] ipHeap, int iSize) {
            // Put the last element at the root
            ipHeap[0] = ipHeap[iSize - 1];
            --iSize;
            int iLasti = 0;
            int i = SwapWithChild(0, ipHeap, iSize);
            while (i != iLasti) {
                iLasti = i;
                i = SwapWithChild(i, ipHeap, iSize);
            }
        }

        /**
         * Exchanges the current index value with that of the parent
         * 
         * @param i
         *            The index of the current value (Child).
         * @param ipHeap
         *            The heap being working with.
         * @return
         */
        int SwapWithParent(int i, int[] ipHeap) {
            if (i < 1) {
                return i;
            }
            int iParent = Parent(i);
            if (ipHeap[i] > ipHeap[iParent]) {
                Swap(i, iParent, ipHeap);
                return iParent;
            } else {
                return i;
            }
        }

        /**
         * Adds an element to the provided heap
         * 
         * @param iNewEntry
         *            The value being added to the heap.
         * @param ipHeap
         *            The heap to add the new value.
         * @param iSize
         *            The current size of the heap.
         */
        void AddElement(int iNewEntry, int[] ipHeap, int iSize) {
            ipHeap[iSize] = iNewEntry;
            int iLasti = iSize;
            int i = SwapWithParent(iLasti, ipHeap);
            while (iLasti != i) {
                iLasti = i;
                i = SwapWithParent(i, ipHeap);
            }
        }

        /**
         * Displays the heap to the console in a linear fashion.
         * 
         * @param ipArray
         *            The heap to be displayed.
         * @param iSize
         *            The current size of the heap.
         */
        static void OutputArray(int[] ipArray, int iSize, int verticalBar) {
            for (int i = 0; i < iSize; ++i) {
                if (i == verticalBar) {
                    System.out.print("|  ");
                }
                System.out.print(ipArray[i] + "  ");
            }
            System.out.println();
        }

        /**
         * Sorts the heap
         * 
         * @param ipHeap
         *            The heap that needs to be sorted.
         * @param iSize
         *            The current size of the heap.
         */
        static void sortRoot(int[] ipHeap, int iSize) {

            // Swap the last element with the root
            Swap(0, iSize - 1, ipHeap);
            iSize--;
            int iLasti = 0;
            int i = SwapWithChild(0, ipHeap, iSize);
            while (i != iLasti) {
                iLasti = i;
                i = SwapWithChild(i, ipHeap, iSize);
            }
        }

        static void heapify(int[] a) {
            for (int iLast = a.length >> 1; iLast >= 0; iLast--) {
                int i = SwapWithChild(iLast, a, a.length);
                while (iLast != i) {
                    iLast = i;
                    i = SwapWithChild(i, a, a.length);
                }
            }

        }

        static void HeapSort2(int[] a, int n) {
            heapify(a);

            for (int i = 0; i < n; ++i) {

                sortRoot(a, n - i);
                OutputArray(a, n, n - 1 - i);
                System.out.println();
            }
        }

        public static void HeapSort1(int[] a, int n){
            int count =n;

            //first place a in max-heap order
            heapify(a, count);

            int end = count - 1;
            while(end > 0){
                //swap the root(maximum value) of the heap with the
                //last element of the heap
                int tmp = a[end];
                a[end] = a[0];
                a[0] = tmp;
                //put the heap back in max-heap order
                siftDown(a, 0, end - 1);
                //decrement the size of the heap so that the previous
                //max value will stay in its proper place
                end--;

            }
        }

        public static void heapify(int[] a, int count){
            //start is assigned the index in a of the last parent node
            int start = (count - 2) / 2; //binary heap

            while(start >= 0){
                //sift down the node at index start to the proper place
                //such that all nodes below the start index are in heap
                //order
                siftDown(a, start, count - 1);
                start--;
            }
            //after sifting down the root all nodes/elements are in heap order
        }

        public static void siftDown(int[] a, int start, int end){
            //end represents the limit of how far down the heap to sift
            int root = start;

            while((root * 2 + 1) <= end){      //While the root has at least one child
                int child = root * 2 + 1;           //root*2+1 points to the left child
                //if the child has a sibling and the child's value is less than its sibling's...
                if(child + 1 <= end && a[child] < a[child + 1])
                    child = child + 1;           //... then point to the right child instead
                if(a[root] < a[child]){     //out of max-heap order
                    int tmp = a[root];
                    a[root] = a[child];
                    a[child] = tmp;
                    root = child;                //repeat to continue sifting down the child now
                }else
                    return;
            }
        }

        static void insertion(int[] a, int n) {
            //System.out.println("********** INSERTION************");
            if (a.length == 0)
                return;
            for (int i = 0; i < a.length; i++) {
                insertionHelper(a, i);
                //OutputArray(a, a.length, i);
            }
        }

        /**
         * A private helper method for the insertion sorting.
         * 
         * @param iaArray
         *            Array to be sorted
         * @param pointer
         *            the current element that needs to be inserted in the proper
         *            order.
         */

        private static void insertionHelper(int[] a, int pointer) {
            // verify pointer is not at the begining of the array
            if (pointer <= 0)
                return;
            // if pointer' value is smaller than the previous element, we need to
            // swap.
            while (pointer > 0 && a[pointer] < a[pointer - 1]) {
                Swap(pointer, pointer - 1, a);
                pointer--;

            }
        }

        public static String myName() {
            return "some name";
        }

    }

Answer 1

出现堆栈溢出异常的原因是因为您在 QuickSort1 中调用了 QuickSort1 方法，并且在实现这样的递归函数时存在限制。您可以使用 -Xss 命令行参数增加调用堆栈大小，例如:

java-Xss4m