java - 我自己的快速排序版本似乎只适用于小数组

Question

我正在尝试在快速排序上实现我自己的版本。当我看到它对小数组进行排序时，我感到非常高兴，但是当我尝试对更大的数组输入(例如 1k、50k、100k、1000k)进行排序时，我感到非常高兴。当我尝试使用数组输入 1000k 时，我发现运行时间比预期的要长，这导致了 stackoverflow。

我很想获得有关我的代码的反馈，我应该在代码中更改哪些内容才能使算法正常工作，并评论为什么它目前不能与我的代码一起工作。

我添加了 run_partition = false，一旦我发现左指针和右指针指向相同的索引。它使得对 100k 的输入数组进行排序成为可能。

// O(nlogn) worst case running time
// O(n) space complexity
import java.util.*;
public class Quicksort {


    public int partition_array(int [] array, int start, int end) {
         // The pivot pointer starts at the first element initially, array index = 0
         // The left pointer points to first element initially

        int left_pointer = start;

        int right_pointer = end;
        int pivot_pointer =  left_pointer;
        boolean run_partition = true; 
        // keep running partition until we return a pivot index, once we return a partition index we can do quicksort on the values left to partition and values to right of partition
     while(run_partition) {


            if( pivot_pointer == left_pointer) {
                // If pivot points towards the left pointer then we have to make sure that all values to the right of pivot, make sure ew can sort duplicate keys too
                while(array[pivot_pointer] <= (array[right_pointer]) && right_pointer != pivot_pointer  ) {
                    right_pointer--;
                 }
                if(left_pointer == right_pointer) {
                // System.out.println(left_pointer + ": is same as  " + right_pointer);
                    run_partition=false;
                   return pivot_pointer;
                }
                // if pivot points towards left pointer and we find out that there exists a right value that is smaller, we have to swap them.
                else if(array[pivot_pointer] > (array[right_pointer]) )  {
                    // System.out.println("Right: " + array[right_pointer] + " is less than pivot_left:  " + array[pivot_pointer]);
                    swap(array, pivot_pointer, right_pointer);
                    pivot_pointer = right_pointer;

                }
                else if( right_pointer < left_pointer){
                break;
                }
                else {
                    right_pointer--;
                }
            }

            if(pivot_pointer == right_pointer) {
                // if pivot_pointer points towards right pointer then we have to make sure that all values to the left is smaller
                while(array[pivot_pointer] > ( array[left_pointer])  && left_pointer != pivot_pointer) {
                    // increment left_pointer until this while condition is no longer true
                    left_pointer++;
                }

                if(pivot_pointer == left_pointer) {
                    run_partition=false;
                    // System.out.println(left_pointer + "is same as " + right_pointer);
                    return pivot_pointer;
                }

                else if(array[pivot_pointer] < (array[left_pointer]))  {
                    // System.out.println("Left: " + array[left_pointer] + " er storre enn pivot:  " + array[pivot_pointer]);
                    swap(array, pivot_pointer, left_pointer);
                    pivot_pointer= left_pointer;
                }
                else if( left_pointer < 0){
                    break;
                    }
                else {
                    left_pointer++;
                }
            }             
        }
            return -1;

    }



    public void quicksort(int [] array, int start, int end) {

        // The pivot pointer starts at the first element initially, array index = 0
        // The left pointer points to first element initially
        // The right pointer points to last element initially
        // All elements to the right of pivot must be greater than pivot
        // All elements to the left of pivot must be smalelr than pivot
        // The pivot pointer starts at the first element initially, array index = 0
         // The left pointer points to first element initially
         if(end<=start || start>=end){
             return;
         }
         if(start <= end) {
            int partition_index = partition_array(array,start,end);
            quicksort(array,start,partition_index-1);
            quicksort(array,partition_index+1,end);

        }
        // System.out.println(Arrays.toString(array));
    }

    public void swap(int[] array, int index_left, int index_right) {
        int temp = array[index_left];
        array[index_left] = array[index_right];
        array[index_right] = temp;
    }        
}

我希望代码适用于更大的数组输入。

Answer 1

算法实现使用递归，给定一个大的输入你的调用堆栈增长，这很可能是导致程序堆栈溢出的原因。您必须实现迭代版本来处理大型数组。