java - 迭代快速排序

Question

我正在尝试实现一个迭代运行的快速排序方法。我使用堆栈来保存信息。它还将使用分区来实现这一点。我知道底部的分区代码部分很好，它只是它的第一个有问题的块。不过，出于某种原因，我的代码并没有按照它的设想做。对java没有太多经验，所以如果有人看到任何会引发标志的错误，将不胜感激！

import java.util.Stack;

public class QuickSort{

// provide non-recursive version of quick sort
// hint: use stack to stored intermediate results
// java.util.Stack can be used as stack implementation
public static <T extends Comparable<T>> void sort(T[] a) {
    Stack<Integer> stack = new Stack<Integer>();

      stack.push(0);
      stack.push(a.length);

      while (!stack.isEmpty())
      {
         int i = 0; 
         int hi = a[i]
         hi = stack.pop();
         int lo = stack.pop();

         if (hi - lo < 2) {
             continue;
             }


         int j = partition(a, lo, hi);
         j = hi + ((lo - hi) / 2);

         stack.push(j - 1);
         stack.push(hi);
         stack.push(lo);
         stack.push(j);    

      } 
         // return;
}

//THIS SECTION OF CODE BELOW SHOULD BE FINE 

// Partition into a[lo..j-1], a[j], a[j+1..hi]
private static <T extends Comparable<T>> int partition(T[] a, int lo, int hi) { 
    int i = lo, j = hi + 1; // left and right scan indices
    T v = a[lo]; // the pivot

    while (true) { // Scan right, scan left, check for scan complete, and exchange
        while (SortUtils.isLessThan(a[++i], v)) {//++i is evaluated to i+1 
            if (i == hi) {
                break;
            }
        }
        while (SortUtils.isLessThan(v, a[--j])) {//--j is evaluated to j-1
            if (j == lo) {
                break;
            }
        }
        if (i >= j) {
            break;
        }

        SortUtils.swap(a, i, j);
    }

    SortUtils.swap(a, lo, j); // Put v = a[j] into position
    return j; 
}

}

测试代码

package edu.csus.csc130.spring2017.assignment2;

import java.util.Arrays;

import org.junit.Assert;
import org.junit.Test;

public class 

QuickSortTest {

@Test
public void testSort1() {
    Integer[] a = {17};
    Integer[] expected = {17};
    QuickSort.sort(a);
    System.out.println(Arrays.toString(a));
    Assert.assertArrayEquals(expected, a);
}

@Test
public void testSort2() {
    Integer[] a = {17, 5};
    Integer[] expected = {5, 17};
    QuickSort.sort(a);
    System.out.println(Arrays.toString(a));
    Assert.assertArrayEquals(expected, a);
}

@Test
public void testSort3() {
    Integer[] a = {64, 18, 74, 89, 58, 17, 48, 44, 92, 88, 78, 80, 75, 25, 77, 18, 39, 95, 11, 2};
    Integer[] expected = {2, 11, 17, 18, 18, 25, 39, 44, 48, 58, 64, 74, 75, 77, 78, 80, 88, 89, 92, 95};
    QuickSort.sort(a);
    System.out.println(Arrays.toString(a));
    Assert.assertArrayEquals(expected, a);
}


}

Answer 1

由于在 partition()hi中是指向数组最后一个元素的索引，因此在代码的初始部分，第二次 push 应该是 push(a.length-1)，即last索引而不是end索引。if 也应该检查 hi - lo < 1 或 lo < hi。

调用分区后，j = 现在排序的枢轴的索引。j = hi + ... 的行应该被删除，因为 partition() 返回要用于 j 的值。由于 a[j] 是已排序的，因此不应将其包含在要递归处理的两个分区中。需要修复两个 stack.push(j ...) 行。

---

使用本地数组作为堆栈的 int 数组的经典 Hoare 分区方案示例：

    public static void qsort(int[] a)
    {
        int[] stk = new int[64];            // stack
        int sti = 0;                        // stack index
        stk[sti++] = a.length-1;
        stk[sti++] = 0;
        while(sti != 0){
            int lo = stk[--sti];
            int hi = stk[--sti];
            while(lo < hi){
                // Hoare partition
                int  md = lo+(hi-lo)/2;
                int  ll = lo-1;
                int  hh = hi+1;
                int p = a[md];
                int t;
                while(true){
                    while(a[++ll] < p);
                    while(a[--hh] > p);
                    if(ll >= hh)
                         break;
                    t     = a[ll];
                    a[ll] = a[hh];
                    a[hh] = t;
                }
                ll = hh++;
                // ll = last left index, hh = first right index
                // push larger partition indexes onto stack
                // loop back for smaller partition
                if((ll - lo) > (hi - hh)){
                    stk[sti++] = ll;
                    stk[sti++] = lo;
                    lo = hh;
                } else {
                    stk[sti++] = hi;
                    stk[sti++] = hh;
                    hi = ll;
                }
            }
        }
    }