非递归QuickSort [英] Non recursive QuickSort

问题描述

我很想知道我的非递归QuickSort算法的实现有一些缺点或隐藏的岩石。应该修改什么才能优化它？当我按照我的方式比较两个对象时会出现什么问题？

I'm curious to know has my implementation of non recursive QuickSort algorithm some drawbacks or hidden rocks. What should be modified in order to optimize it? And what problems could happen when comparing two objects in the way I do it?

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这种排序的最佳集合？

And is ArrayList the best collection for this kind of sort?

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

考虑到建议修改后的代码

The code after modifying in consideration of the suggestions

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

这篇关于非递归QuickSort的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！