我正在尝试在quicksort上实现我自己的版本当我看到它为小数组排序时,我非常高兴,但是当我尝试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;
    }
}

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

最佳答案

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

07-24 09:49
查看更多