面试题目之 ----使用非迭代方法快速排序

1.教科書上使用迭代的方法進行快速排序，原则上所有的迭代都可以用自定义栈来转换为非迭代算法。

假如最少两个构成一段， 当前的分段个数一定不会超过length/2.
用两个数组表示各个分段：
int[] low = new int[length/2];
int[] high = new int[length/2];

每次循环只拆分栈顶的那个分段，用index 变量记录栈顶，并加入第一个根分段：

int index = 0;
low[index] = 0;
high[index] = values.length - 1;

然后使用while循环
while (index >= 0) {
  int plow = low[index];
  int phigh = high[index];
  int pivoit = low[index];
  int pivoitVluae = values[pivoit];
 
  Onetimequicksort();
}

package interview;

public class QuickSortNotRecursive {

	public static void main(String[] args) {
		int[] values = new int[] {
				7, 13, 4, 246
		};
		quickSort(values.length, values);
		for(int i = 0; i < values.length; ++ i) {
			System.out.println(values[i]);
		}
	}

	public static void quickSort(int length, int[] values) {
		int[] low = new int[length];
		int[] high = new int[length];
		int index = 0;
		low[index] = 0;
		high[index] = values.length - 1;
		while (index >= 0) {
			int plow = low[index];
			int phigh = high[index];
			int pivoit = low[index];
			int pivoitVluae = values[pivoit];
			while (plow < phigh) {
				while (plow <= phigh) {
					if (values[phigh] >= pivoitVluae) {
						values[pivoit] = values[phigh];
						pivoit = phigh;
						phigh --;
						break;
					}else {
						phigh --;
					}
				}
				while (plow <= phigh) {
					if (values[plow] < pivoitVluae) {
						values[pivoit] = values[plow];
						pivoit = plow;
						plow++;
						break;
					}else {
						plow ++;
					}
				}
			}
			values[pivoit] = pivoitVluae;

			int topLow = low[index];
			int topHigh = high[index];
			index--;
			if (pivoit - 1 > topLow) {
				index++;
				low[index] = topLow;
				high[index] = pivoit - 1;
			}
			if (pivoit + 1 < topHigh) {
				index++;
				low[index] = pivoit + 1;
				high[index] = topHigh;
			}
		}
	}
}

经过测试，工作正常。

采用教科书的更优化的一趟快速排序

	public static void quickSort2(int length, int[] values) {
		if (values.length < 2) {
			return;
		}
		int[] low = new int[(length) / 2];
		int[] high = new int[(length) / 2];
		int topIndex = 0;
		low[topIndex] = 0;
		high[topIndex] = values.length - 1;
		while (topIndex >= 0) {
			int plow = low[topIndex];
			int phigh = high[topIndex];
			int pivoitVluae = values[plow];

			while (plow < phigh) {
				while (plow < phigh) {
					if (values[phigh] > pivoitVluae) {
						values[plow] = values[phigh];
						break;
					} else {
						phigh--;
					}
				}
				while (plow < phigh) {
					if (values[plow] < pivoitVluae) {
						values[phigh] = values[plow];
						break;
					} else {
						plow++;
					}
				}
			}
			values[plow] = pivoitVluae;
			
			int topLow = low[topIndex];
			int topHigh = high[topIndex];
			topIndex--;
			if (plow - 1 > topLow) {
				topIndex++;
				low[topIndex] = topLow;
				high[topIndex] = plow - 1;
			}
			if (plow + 1 < topHigh) {
				topIndex++;
				low[topIndex] = plow + 1;
				high[topIndex] = topHigh;
			}
		}
	}