内容简介：快速排序算法是重要的排序算法之一。与合并排序类似，quicksort也采用了分而治之，因此在Java中使用递归实现快速排序算法很容易，但编写quicksort的迭代版本稍微困难一些。这就是为什么面试官现在要求在不使用递归的情况下实现快速排序。面试首先要用Java中的QuasQuo排序算法编写一个程序来排序数组，很有可能你会得到一个递归排序的快速排序，如这里所示。然后，面试官会要求您使用迭代编写相同的算法。如果您还记得，在解决没有递归的二叉树问题时，我们使用堆栈替换递归。您可以在这里使用相同的技术在Java中
快速 排序算法 是重要的 排序 算法之一。与合并排序类似，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循环和堆栈实现快速排序，而不使用递归。这也被称为迭代快速排序算法。
<b>import</b> java.util.Arrays;
<b>import</b> java.util.Scanner;
<b>import</b> java.util.Stack;
<font><i>/**
* Java Program to implement Iterative QuickSort Algorithm, without recursion.
*
* @author WINDOWS 8
*/</i></font><font>
<b>public</b> <b>class</b> Sorting {
<b>public</b> <b>static</b> <b>void</b> main(String args) {
<b>int</b> unsorted = {34, 32, 43, 12, 11, 32, 22, 21, 32};
System.out.println(</font><font>"Unsorted array : "</font><font> + Arrays.toString(unsorted));
iterativeQsort(unsorted);
System.out.println(</font><font>"Sorted array : "</font><font> + Arrays.toString(unsorted));
}
</font><font><i>/*
* iterative implementation of quicksort sorting algorithm.
*/</i></font><font>
<b>public</b> <b>static</b> <b>void</b> iterativeQsort(<b>int</b> numbers) {
Stack stack = <b>new</b> Stack();
stack.push(0);
stack.push(numbers.length);
<b>while</b> (!stack.isEmpty()) {
<b>int</b> end = stack.pop();
<b>int</b> start = stack.pop();
<b>if</b> (end - start < 2) {
<b>continue</b>;
}
<b>int</b> p = start + ((end - start) / 2);
p = partition(numbers, p, start, end);
stack.push(p + 1);
stack.push(end);
stack.push(start);
stack.push(p);
}
}
</font><font><i>/*
* Utility method to partition the array into smaller array, and
* comparing numbers to rearrange them as per quicksort algorithm.
*/</i></font><font>
<b>private</b> <b>static</b> <b>int</b> partition(<b>int</b> input, <b>int</b> position, <b>int</b> start, <b>int</b> end) {
<b>int</b> l = start;
<b>int</b> h = end - 2;
<b>int</b> piv = input[position];
swap(input, position, end - 1);
<b>while</b> (l < h) {
<b>if</b> (input[l] < piv) {
l++;
} <b>else</b> <b>if</b> (input[h] >= piv) {
h--;
} <b>else</b> {
swap(input, l, h);
}
}
<b>int</b> idx = h;
<b>if</b> (input[h] < piv) {
idx++;
}
swap(input, end - 1, idx);
<b>return</b> idx;
}
</font><font><i>/**
* Utility method to swap two numbers in given array
*
* @param arr - array on which swap will happen
* @param i
* @param j
*/</i></font><font>
<b>private</b> <b>static</b> <b>void</b> swap(<b>int</b> arr, <b>int</b> i, <b>int</b> j) {
<b>int</b> 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]
</font>
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持 码农网
本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。
Blockchain Basics
Daniel Drescher / Apress / 2017-3-16 / USD 20.99
In 25 concise steps, you will learn the basics of blockchain technology. No mathematical formulas, program code, or computer science jargon are used. No previous knowledge in computer science, mathema......一起来看看 《Blockchain Basics》 这本书的介绍吧!
