m% = 16000
DIM SHARED s(m%)
RANDOMIZE TIMER
FOR i% = 1 TO m%
    s(i%) = RND
NEXT

QSort3 1, m%

调用排序

---------------------------------------------------
第一种: 标准的递归形式

SUB QuickSort (l%, h%)
IF l% < h% THEN
  IF h% - l% = 1 THEN
     IF s(l%) > s(h%) THEN SWAP s(l%), s(h%)
  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% - i%) THEN
        QuickSort l%, i% - 1
        QuickSort i% + 1, h%
     ELSE
        QuickSort i% + 1, h%
        QuickSort l%, i% - 1
     END IF
  END IF
END IF
END SUB
-------------------------------------------------------
第二种: 用数组替换递归

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

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

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
     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%)
     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

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

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

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

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

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

评论