java—是否可以将递归方法更改为迭代方法?

np8igboo  于 2021-06-30  发布在  Java
关注(0)|答案(1)|浏览(477)

我正在写一个快速排序算法,用随机轴对数字进行排序。如何将快速排序方法从递归更改为迭代?我有一个递归的排序方法,但是我需要迭代的方法。在排序方法中,是否可以从递归方法更改为迭代方法,还是必须更改整个代码?
这是我所有的密码

public class Main {

    public static void main(String[] args) {
        long start = System.currentTimeMillis();
        ArrayList time = new ArrayList();
        for (int k = 1; k < 1000000; k++) {
            time.add(k);
        }

        int[] tall = new int[1000000];
        int index = 0;
        int n = 1000000;

        File text = new File("/Users/sasan/IdeaProjects/File.txt");

        try {
            Scanner scan = new Scanner(text);

            while (scan.hasNextLine() && index < 1000000) {
                tall[index] = scan.nextInt();
                index++;
            }
            scan.close();
        } catch (IOException e) {
            System.out.println("Problem with file");
            e.printStackTrace();
        }

        int l = tall.length;

        sort(tall, 0, l-1);

        System.out.println("Sorted array");
        printArray(tall);

        System.out.println("");

        long end = System.currentTimeMillis();
        System.out.print("Execution Time is: ");
        System.out.print((end - start));
    }

    static void random(int tall[],int low,int high)
    {
        Random rand= new Random();
        int pivot = rand.nextInt(high-low)+low;

        int temp1=tall[pivot];
        tall[pivot]=tall[high];
        tall[high]=temp1;
    }

    /* This function takes last element as pivot,
    places the pivot element at its correct
    position in sorted array, and places all
    smaller (smaller than pivot) to left of
    pivot and all greater elements to right
    of pivot */
    static int partition(int tall[], int low, int high)
    {
        // pivot is choosen randomly
        random(tall,low,high);
        int pivot = tall[high];

        int i = (low-1); // index of smaller element
        for (int j = low; j < high; j++)
        {
            // If current element is smaller than or
            // equal to pivot
            if (tall[j] < pivot)
            {
                i++;

                // swap arr[i] and arr[j]
                int temp = tall[i];
                tall[i] = tall[j];
                tall[j] = temp;
            }
        }

        // swap arr[i+1] and arr[high] (or pivot)
        int temp = tall[i+1];
        tall[i+1] = tall[high];
        tall[high] = temp;

        return i+1;
    }

    /* The main function that implements QuickSort()
    tall[] --> Array to be sorted,
    low --> Starting index,
    high --> Ending index */
    static void sort(int tall[], int low, int high)
    {
        if (low < high)
        {
            /* pi is partitioning index, tall[pi] is
            now at right place */
            int pi = partition(tall, low, high);

            // Recursively sort elements before
            // partition and after partition
            sort(tall, low, pi-1);
            sort(tall, pi+1, high);
        }
    }

    /* A utility function to print array of size n */
    static void printArray(int tall[])
    {
        int n = tall.length;
        for (int i = 0; i < n; ++i)
            System.out.print(tall[i]+" ");
        System.out.println();
    }

    // Driver Code
}
ycl3bljg

ycl3bljg1#

通常可以将递归方法转换为迭代方法,尽管使用递归的要点是,通常在最方便的时候选择它。像快速排序这样的分而治之算法正是递归的一个很好的候选者。
要将递归方法转换为迭代方法,基本上使用“stack”对象(java提供了stack类来帮助实现这一点):它本质上存储了每次迭代需要操作的参数。然后,在调用递归方法之前,将用于调用它的参数放在堆栈顶部。每一次迭代都相当于从方法中“返回”最新的参数(本质上,您是在模拟java在调用方法时所经历的过程。)
所以模式是这样的:

Stack<Paraneters> stack = new Stack();
stack.push(new Parameters(0, size);
while (!stack.empty()) {
    Parameters params = stack.pop();
    int lo = params.lo;
    int hi = params.hi;

    if (lo < hi) {
        int pivot = partition(lo, hi);
        stack.push(new Parameters(lo, pivot-1));
        stack.push(new Parameters(pivot+1, hi));
    }
}

对于这个简单的示例,parameters对象实际上可能只是一个2长度的int数组,但是对于更复杂的参数组合,您可能最终会构造一个 Package 器类(使用递归在实践中更方便的另一个原因。)

相关问题