非递归写快速排序着实比较少见，不过练练手总是好的。需要用到栈，注意压栈的顺序。代码如下：
/** * 快速排序-非递归版本 */ void quickSortIter(int a[], int n) { Stack *stack = stackNew(n); int l = 0, u = n-1; int p = partition(a, l, u); <span>if</span> (p-1 > l) { //左半部分两个边界值入栈 push(stack, p-1); push(stack, l); } <span>if</span> (p+1 < u) { //右半部分两个边界值入栈 push(stack, u); push(stack, p+1); } <span>while</span> (!IS_EMPTY(stack)) { //栈不为空，则循环划分过程 l = pop(stack); u = pop(stack); p = partition(a, l, u); <span>if</span> (p-1 > l) { push(stack, p-1); push(stack, l); } <span>if</span> (p+1 < u) { push(stack, u); push(stack, p+1); } }}
复制代码
随机算法涉及大量概率论知识，有时候难得去仔细看推导过程，当然能够完全了解推导的过程自然是有好处的，如果不了解推导过程，至少记住结论也是必要的。本文总结最常见的一些随机算法的题目，是几年前找工作的时候写的。需要说明的是，这里用到的随机函数 randInt(a, b) 假定它能随机的产生范围 [a,b] 内的整数，即产生每个整数的概率相等（虽然在实际中并不一定能实现，不过不要太在意，这个世界很多事情都很随机）。本文代码在 这里。
1.随机排列数组假设给定一个数组 A，它包含元素 1 到 N，我们的目标是构造这个数组的一个均匀随机排列。
一个常用的方法是为数组每个元素 A[i] 赋一个随机的优先级 P[i]，然后依据优先级对数组进行排序。比如我们的数组为 A = {1， 2， 3， 4}，如果选择的优先级数组为 P = {36， 3， 97， 19}，那么就可以得到数列 B={2, 4, 1, 3}，因为 3 的优先级最高（为97），而 2 的优先级最低（为3）。这个算法需要产生优先级数组，还需使用优先级数组对原数组排序，这里就不详细描述了，还有一种更好的方法可以得到随机排列数组。
产生随机排列数组的一个更好的方法是原地排列（in-place）给定数组，可以在 O(N) 的时间内完成。伪代码如下：
RANDOMIZE-IN-PLACE ( A , n ) for i ←1 to n do swap A[i] ↔ A[RANDOM(i , n )] 复制代码如代码中所示，第 i 次迭代时，元素 A[i] 是从元素 A[i...n]中随机选取的，在第 i 次迭代后，我们就再也不会改变 A[i]。
A[i] 位于任意位置j的概率为 1/n。这个是很容易推导的，比如 A[1] 位于位置 1 的概率为 1/n，这个显然，因为 A[1] 不被1到n的元素替换的概率为 1/n，而后就不会再改变 A[1] 了。而 A[1] 位于位置 2 的概率也是 1/n，因为 A[1] 要想位于位置 2，则必须在第一次与 A[k] (k=2...n) 交换，同时第二次 A[2] 与 A[k]替换，第一次与 A[k] 交换的概率为(n-1)/n，而第二次替换概率为 1/(n-1)，所以总的概率是 (n-1)/n * 1/(n-1) = 1/n。同理可以推导其他情况。
当然这个条件只能是随机排列数组的一个必要条件，也就是说，满足元素 A[i] 位于位置 j 的概率为1/n 不一定就能说明这可以产生随机排列数组。因为它可能产生的排列数目少于 n!，尽管概率相等，但是排列数目没有达到要求，算法导论上面有一个这样的反例。
算法 RANDOMIZE-IN-PLACE可以产生均匀随机排列，它的证明过程如下：
首先给出k排列的概念，所谓 k 排列就是从n个元素中选取k个元素的排列，那么它一共有 n!/(n-k)! 个 k 排列。
循环不变式：for循环第i次迭代前，对于每个可能的i-1排列，子数组A[1...i-1]包含该i-1排列的概率为 (n-i+1)! / n!。
初始化：在第一次迭代前，i=1，则循环不变式指的是对于每个0排列，子数组A[1...i-1]包含该0排列的概率为 (n-1+1)! / n! = 1。A[1...0]为空的数组，0排列则没有任何元素，因此A包含所有可能的0排列的概率为1。不变式成立。
维持：假设在第i次迭代前，数组的i-1排列出现在 A[1...i-1] 的概率为 (n-i+1) !/ n!，那么在第i次迭代后，数组的所有i排列出现在 A[1...i] 的概率为 (n-i)! / n!。下面来推导这个结论：
考虑一个特殊的 i 排列 p = {x1, x2, ... xi}，它由一个 i-1 排列 p\' ={x1, x2,..., xi−1} 后面跟一个 xi 构成。设定两个事件变量E1和E2：
E1为该算法将排列 p\' 放置到 A[1...i-1]的事件，概率由归纳假设得知为 Pr(E1) = (n-i+1)! / n!。
E2为在第 i 次迭代时将 xi 放入到 A[i] 的事件。 因此我们得到 i 排列出现在 A[1...i] 的概率为 Pr {E2 ∩ E1} = Pr {E2 | E1} Pr {E1}。而Pr {E2 | E1} = 1/(n − i + 1)，所以 Pr {E2 ∩ E1} = Pr {E2 | E1} Pr {E1}= 1 /(n − i + 1) * (n − i + 1)! / n! = (n − i )! / n!。
结束：结束的时候 i=n+1，因此可以得到 A[1...n] 是一个给定 n 排列的概率为 1/n！。