-------------------------------------------------------
第二种: 用数组替换递归

SUB QSort2 (l%, m%)
DIM q%((LOG(m%) / LOG(2)) * 10)
h% = m%
DO
IF l% < h% THEN
  IF h% - l% = 1 THEN
     IF s(l%) > s(h%) THEN SWAP s(l%), s(h%)
     l% = h% + 1
     h% = q%(k%)
     k% = k% - 1
  ELSE
     r% = (h% + l%) \ 2
     SWAP s(h%), s(r%)
     p = s(h%)
     i% = l%
     j% = h%
     DO
      DO WHILE (i% < j%) AND (s(i%) <= p)
         i% = i% + 1
      LOOP
      DO WHILE (j% > i%) AND (s(j%) >= p)
         j% = j% - 1
      LOOP
      IF i% < j% THEN SWAP s(i%), s(j%)
     LOOP WHILE i% < j%
     SWAP s(i%), s(h%)
     IF i% - l% > 1 THEN
        k% = k% + 1
        q%(k%) = h%
        h% = i% - 1
     ELSE
        l% = i% + 1
     END IF
  END IF
ELSE
     l% = h% + 1
     h% = q%(k%)
     k% = k% - 1
END IF
LOOP UNTIL l% >= (m% - 1)
END SUB

--------------------------------------------------------
在 Qsort2 形式中,因为按顺序分组,所以失去了动态的特性
而标志数组的在一般的情况下是不会溢出的,除非是恶意的定位
这个时候最大层数有可能达到 m/2 层
而普通情况下应该最多只有 2*(log(m)/log(2)) 层

为了保留动态的处理顺序,变形出 Qsort3
用了二维数组去保存上下两界,能不能减少层数,也不好说
因为加了一维来代替层数去了,
而因为处理数据的不定原因,我还去掉了 rnd 的动态

在 Qsort3 里,我还加了一句 goto
只是为了省几下键盘,在这里使用还算情有可愿吧.

更改形式的目的是为了避免堆栈溢出的麻烦,
但在 XP 下好像连标准递归都没出现溢出现象,
不知道是什么回事.
而 Qsort2, Qsort3 不用递归的好处就是连数组都可以作为参数
省略共享,如果在递归中不使用共享而用参数形式的话还得处理一些地址问题

欢迎大家提出意见,因为我文化水平实现不高,希望能得到大家的指点.

-----------------------------------------------------
第三种: 保留动态特性的替换

SUB QSort3 (l%, m%)
h% = m%
DIM q%((LOG(h%) / LOG(2)) * 10, 1)
DO
IF l% < h% THEN
  IF h% - l% = 1 THEN
     IF s(l%) > s(h%) THEN SWAP s(l%), s(h%)
     GOTO 10
  ELSE
     r% = INT(RND * (h% - l% + 1)) + l%
     SWAP s(h%), s(r%)
     p = s(h%)
     i% = l%
     j% = h%
     DO
      DO WHILE (i% < j%) AND (s(i%) <= p)
         i% = i% + 1
      LOOP
      DO WHILE (j% > i%) AND (s(j%) >= p)
         j% = j% - 1
      LOOP
      IF i% < j% THEN SWAP s(i%), s(j%)
     LOOP WHILE i% < j%
     SWAP s(i%), s(h%)
     IF i% - l% < h% - l% THEN
        k% = k% + 1
        q%(k%, 0) = i% + 1
        q%(k%, 1) = h%
        h% = i% - 1
     ELSE
        k% = k% + 1
        q%(k%, 0) = l%
        q%(k%, 1) = i% - 1
        l% = i% + 1
     END IF
  END IF
ELSE
10
     l% = q%(k%, 0)
     h% = q%(k%, 1)
     k% = k% - 1
END IF
LOOP UNTIL k% < 0
END SUB

------------------------------------------
我再把标准递归的动态特性取消掉,
速度反而更快了一点点,
牺牲的只是一点处理范围,
因为在动态里面,
      含动态递归的最高层数 < log(m)/log(2)+ C
而摘除动态后递归的最高层数 > log(m)/log(2)+ C


SUB QuickSort2 (l%, h%)
IF l% >= h% THEN exit sub
  IF h% - l% = 1 THEN
     IF s(l%) > s(h%) THEN SWAP s(l%), s(h%)
  ELSE
     p = s(h%) : i% = l% : j% = h%-1
     DO
      DO WHILE (i% < j%) AND (s(i%) <= p) : i% = i% + 1 :  LOOP
      DO WHILE (j% > i%) AND (s(j%) >= p) : j% = j% - 1 :  LOOP
      IF i% < j% THEN SWAP s(i%), s(j%)
     LOOP WHILE i% < j%
      SWAP s(i%), s(h%)
      QuickSort2 l%, i% - 1
      QuickSort2 i% + 1, h%
  END IF
END SUB

  $请大家千万不要用递归。。。
   用do...loop
   if xxx then exit sub
   单层入栈总比多层入栈好。。。$
  $不过，用def fn创建的函数做递归我决不反对。$

著："$"是引号的一种形式

2^15 = 32768

如果中间保存的变量不多的话,
32768个数值可以在15次递归以内完成(动态<15次)
所以还是能接受的.

我以前做CMOS6.00就遇到过。。。
call了好多(大约12次)次后，WIN下就显示stack oerflow，dos下显示乱吗后死机

我早就提出递归的方法不合理了。。。

一般的栈空间是2K
如果中间变量不多的话
递归个六七十次还是可以的

至于faintzw说的预置栈空间的clear,,stack&
实在也是有限

能不用还是尽量避免递归的好,
虽然执行质量高,
一旦扩展处理范围溢出就不好办了.

脑袋益处就不好办了