内容简介：快速排序算法是重要的排序算法之一。与合并排序类似，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>
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持 码农网
猜你喜欢:
- 迭代器萃取与反向迭代器
- 浅谈python可迭代对象，迭代器
- 可迭代对象，迭代器(对象)，生成器(对象)
- 终于把动态规划与策略迭代、值迭代讲清楚了
- 终于把动态规划与策略迭代、值迭代讲清楚了
- 搞清楚 Python 的迭代器、可迭代对象、生成器
本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。
Java语言程序设计
（美） Y. Daniel Liang / 李娜 / 机械工业出版社 / 2011-6 / 75.00元
本书是Java语言的经典教材，多年来畅销不衰。本书全面整合了Java 6的特性，采用“基础优先，问题驱动”的教学方式，循序渐进地介绍了程序设计基础、解决问题的方法、面向对象程序设计、图形用户界面设计、异常处理、I/O和递归等内容。此外，本书还全面且深入地覆盖了一些高级主题，包括算法和数据结构、多线程、网络、国际化、高级GUI等内容。 本书中文版由《Java语言程序设计：基础篇》和《Java语......一起来看看 《Java语言程序设计》 这本书的介绍吧!
