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>