Java不用递归的迭代快速排序示例

19-02-25 jdon
         

快速排序算法是重要的排序算法之一。与合并排序类似,quicksort也采用了分而治之,因此在Java中使用递归实现快速排序算法很容易,但编写quicksort的迭代版本稍微困难一些。这就是为什么面试官现在要求在不使用递归的情况下实现快速排序。面试首先要用Java中的QuasQuo排序算法编写一个程序来排序数组,很有可能你会得到一个递归排序的快速排序,如这里所示。然后,面试官会要求您使用迭代编写相同的算法。

如果您还记得,在解决没有递归的二叉树问题时,我们使用堆栈替换递归。您可以在这里使用相同的技术在Java中编写迭代快速排序程序。堆栈实际上模拟了递归。

迭代快速排序算法

我在工程课上学习了Quicksort,这是当时我能理解的少数算法之一。因为它是一个分而治之的算法,所以您可以选择一个轴并划分数组。与合并排序不同,合并排序也是一种分而治之的算法,所有重要的工作都发生在合并步骤上,而在快速排序中,真正的工作发生在分而治之的步骤上,合并步骤则不重要。

无论您是实现迭代解决方案还是递归解决方案,算法的工作都将保持不变。在迭代解决方案中,我们将使用堆栈而不是递归。下面是在Java中实现迭代快速排序的步骤:

1.将范围(0…n)推入堆栈

2.使用数据透视表对给定数组进行分区

3.弹出顶部元素。

4.如果范围有多个元素,将分区(索引范围)推入堆栈

5.执行上述3个步骤,直到堆栈为空

您可能知道,尽管编写递归算法很容易,但它们总是比迭代算法慢。所以,当面试官要求你从时间复杂度的角度来选择一种方法时,你会选择哪种版本?

好吧,递归和迭代快速排序在平均情况情况下都是O(n log n)在最坏情况情况下都是O(n^2),但是递归版本更短更清晰。迭代速度更快,可以使用堆栈模拟递归。

这里是我们的Java程序示例,使用for循环和堆栈实现快速排序,而不使用递归。这也被称为迭代快速排序算法。

import java.util.Arrays;
import java.util.Scanner;
import java.util.Stack;

/**
 * Java Program to implement Iterative QuickSort Algorithm, without recursion.
 *
 * @author WINDOWS 8
 */
public class Sorting {

    public static void main(String args) {

        int unsorted = {34, 32, 43, 12, 11, 32, 22, 21, 32};
        System.out.println("Unsorted array : " + Arrays.toString(unsorted));

        iterativeQsort(unsorted);
        System.out.println("Sorted array : " + Arrays.toString(unsorted));
    }


    /*
     * iterative implementation of quicksort sorting algorithm.
     */
    public static void iterativeQsort(int numbers) {
        Stack stack = new Stack();
        stack.push(0);
        stack.push(numbers.length);

        while (!stack.isEmpty()) {
            int end = stack.pop();
            int start = stack.pop();
            if (end - start < 2) {
                continue;
            }
            int p = start + ((end - start) / 2);
            p = partition(numbers, p, start, end);

            stack.push(p + 1);
            stack.push(end);

            stack.push(start);
            stack.push(p);

        }
    }

    /*
     * Utility method to partition the array into smaller array, and
     * comparing numbers to rearrange them as per quicksort algorithm.
     */
    private static int partition(int input, int position, int start, int end) {
        int l = start;
        int h = end - 2;
        int piv = input[position];
        swap(input, position, end - 1);

        while (l < h) {
            if (input[l] < piv) {
                l++;
            } else if (input[h] >= piv) {
                h--;
            } else {
                swap(input, l, h);
            }
        }
        int idx = h;
        if (input[h] < piv) {
            idx++;
        }
        swap(input, end - 1, idx);
        return idx;
    }

    /**
     * Utility method to swap two numbers in given array
     *
     * @param arr - array on which swap will happen
     * @param i
     * @param j
     */
    private static void swap(int arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

}

Output:
Unsorted array : [34, 32, 43, 12, 11, 32, 22, 21, 32]
Sorted array : [11, 12, 21, 22, 32, 32, 32, 34, 43][/i][/i]

         

1