今天想到一个问题,我记得《剑指offer》这本书里面说过:递归都可以转换成循环。那么怎么用循环来实现快速排序,我迄今为止看到的所有快速排序都是用的递归,于我试着写,想了半个小时居然一点头绪都没有。
有哪位大大能够写循环实现的,想开开眼界
用栈储存,对着改就好了
function qsort_with_loop(arr) {
let stack = [];
stack.push([0, arr.length - 1]);
while (stack.length) {
let _ = stack.pop();
let i = l = _[0];
let j = r = _[1];
let mid = arr[(i + j) >> 1];
do {
while (arr[i] < mid) ++i;
while (arr[j] > mid) --j;
if (i <= j) {
let t = arr[i];
arr[i] = arr[j];
arr[j] = t;
++i;
--j;
}
} while (i <= j);
if (i < r) stack.push([i, r]);
if (l < j) stack.push([l, j]);
}
}
写了两个版本,你对照一下: https://jsfiddle.net/hsfzxjy/ob8x16uz/4/
可以用栈储存状态 也就是高级语言实现递归的本质
import java.util.Stack;
//快速排序的非递归实现,利用系统的栈stack
public class QuickSortNonRecursion {
public static void main(String[] args) {
QuickSortNonRecursion qsnr = new QuickSortNonRecursion();
int[] array = {0, 2, 11, 121, 18, 99, 3, 5, 101, 22, 9, 100};
qsnr.quicksort(array);
for (int i : array) {
System.out.print(i + " ");
}
}
public void quicksort(int[] array) {
if (array == null || array.length == 1) return;
//存放开始与结束索引
Stack<Integer> s = new Stack<Integer>();
//压栈
s.push(0);
s.push(array.length - 1);
//利用循环里实现
while (!s.empty()) {
int right = s.pop();
int left = s.pop();
//如果最大索引小于等于左边索引,说明结束了
if (right <= left) continue;
int i = partition(array, left, right);
if (left < i - 1) {
s.push(left);
s.push(i - 1);
}
if (i + 1 < right) {
s.push(i+1);
s.push(right);
}
}
}
//找到轴心,进行交换
public int partition (int[] data, int first, int end)
{
int temp;
int i=first,j=end;
if(first<end)
{
temp=data[i];
//当i=j的时候,则说明扫描完成了
while(i<j)
{
//从右边向左边扫描找到一个小于temp的元素
while(j>i&&data[j]>temp)j--;
if(i<j)
{
//将该元素赋值给temp
data[i]=data[j];
//赋值后就应该将i+1指向下一个序号
i++;
}
//然后从左边向右边开始扫描,找到一个大于temp的元素
while(i<j&&temp>data[i])i++;
if(i<j)
{
//将该元素赋值给temp
data[j]=data[i];
//赋值后就应该将j-1指向前一个序号
j--;
}
}
//将轴数据放在i位置中
data[i]=temp;
}
return i;
}
}