java - 非递归QuickSort

我很好奇知道我的非递归QuickSort算法的实现存在一些缺点或隐患。为了优化它应该修改什么？以我的方式比较两个对象时，会发生什么问题？

public class QuickSort <T extends Number> {

private Integer first, last, boundLo, boundHi, pivot;
Integer temp[] = {0, 0};

public void sort(NewArrayList<T> vect) {
    Deque<Integer[]> stack = new ArrayDeque<Integer[]>();

    first = 0;
    last = vect.size() - 1;
    stack.push(new Integer[] {first, last});

    while(!stack.isEmpty()) {
        sortStep(vect, stack);
    }
}

private void sortStep(NewArrayList<T> vect, Deque<Integer[]> stack) {
    // initialize indices
    temp = stack.pop();
    first = temp[0];
    last = temp[1];

    boundLo = first;
    boundHi = last;
    pivot = last;

    while(first < last) {
        if(vect.get(first).doubleValue() >= vect.get(pivot).doubleValue()) {
            last--;
            if(first != last)
                vect.swap(first, last);
            vect.swap(last, pivot);
            pivot--;
        }
        else first++;
    }

    if(boundLo < (pivot - 1))
        stack.add(new Integer[] {boundLo, pivot - 1});

    if(boundHi > (pivot + 1))
        stack.add(new Integer[] {pivot + 1, boundHi});

}

}

ArrayList是这种类型的最佳集合吗？

public class  NewArrayList<T> extends ArrayList<T> {

public NewArrayList() {
    super();
}

public void swap(int index1, int index2) {
    this.set(index1, this.set(index2, this.get(index1)));
}
}

考虑建议修改后的代码

public class QuickSort <T extends Number> {

private int first, last, boundLo, boundHi, pivot;
int temp[] = {0, 0};

public QuickSort() {
    super();
}

public void sort(List<T> list) {

    Deque<int[]> stack = new ArrayDeque<int[]>();

    first = 0;
    last = list.size() - 1;

    stack.push(new int[] {first, last});

    while(!stack.isEmpty()) {
        sortStep(list, stack);
    }
}

private void sortStep(List<T> list, Deque<int[]> stack) {

    temp = stack.pop();
    first = temp[0];
    last = temp[1];

    boundLo = first;
    boundHi = last;
    pivot = last;

    while(first < last) {
        if(list.get(first).doubleValue() >= list.get(pivot).doubleValue()) {
            last--;
            if(first != last)
                Collections.swap(list, first, last);
            Collections.swap(list, last, pivot);
            pivot--;
        }
        else first++;
    }

    if(boundLo < (pivot - 1))
        stack.add(new int[] {boundLo, pivot - 1});

    if(boundHi > (pivot + 1))
        stack.add(new int[] {pivot + 1, boundHi});
}

}

最佳答案

public class Sort {
    /** Returns a sorted list of attributes. */
    protected int[] sortAttributes1(int[] array) {

        Queue<Range> queue = new ArrayDeque<Range>();

        while (!queue.isEmpty()) {
            Range range = queue.poll();
            if (range.isEmpty()) {
                continue;
            }
            int left = range.getLeft();
            int right = range.getRight();
            // partition the range
            right = partition(array, left, right);
            Range lr = new Range(range.getLeft(), right - 1);
            Range rr = new Range(right + 1, range.getRight());

            queue.add(lr);
            queue.add(rr);
        }
        return array;
    }


    private int partition(int[] array, int left, int right) {
        int pivot = right - left >>> 2;


        while (left <= right) {
            int pivotVal = array[pivot];
            if (array[left] <= pivotVal) {
                left++;
                continue;
            }
            right--;
            if (left == right)continue;
            int temp = array[left];
            array[left] = array[right];
            array[right] = temp;
        }

        int temp = array[pivot];
        array[pivot] = array[right];
        array[right] = temp;

        return right;
    }
}

关于java - 非递归QuickSort，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/19124752/