java - 非递归快速排序

Question

我很想知道我的非递归快速排序算法的实现是否存在一些缺点或隐藏的问题。为了优化它应该修改什么？以我的方式比较两个对象时可能会出现什么问题？

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