快速排序与归并排序的非递归实现
一、快速排序（非递归）
1. 原理
- 在每一个待排元素所确定的待排序区间内，把待排序元素用基准排序一个个排好。等到把所有待排序区间对应的一个个待排序元素都排好后，整个数组就排好了。
（在区间内进行基准排序时，默认以区间第一个元素为待排序元素）
用基准排序把每一个元素在对应已知的待排序范围排好，因为每排好一个元素，此元素排序位置确定且其排出的左小右大性质能缩小剩余的元素的待排序范围区域，所以每当一个元素排好后，其余元素对应的已知待排序范围就会发生变化，所以元素所在的待排序区域是经过动态变化来的。
2. 实现
public static void quickSortNonR(int[] array) {
Stack<Integer> stack = new Stack<>();
int left = 0;
int right = array.length - 1;
int pivot = partition(array, left, right);
if (pivot - 1 > left) {
stack.push(left);
stack.push(pivot - 1);
}
if (pivot + 1 < right) {
stack.push(pivot + 1);
stack.push(right);
}
while (!stack.isEmpty()) {
right = stack.pop();
left = stack.pop();
pivot = partition(array, left, right);
if (pivot - 1 > left) {
stack.push(left);
stack.push(pivot - 1);
}
if (pivot + 1 < right) {
stack.push(pivot + 1);
stack.push(right);
}
}
}
// 基准排序挖坑法实现
private static int {
array[left];
(left < right) {
(left < right && array[right] >= key) {
right--;
}
array[left] = array[right];
(left < right && array[left] <= key) {
left++;
}
array[right] = array[left];
}
array[left] = key;
left;
}
