非递归QuickSort

Question

我很想知道我的非递归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});
}

}

Answer 1

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;
    }    
}