非递归QuickSort

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

public class QuickSort  { private Integer first, last, boundLo, boundHi, pivot; Integer temp[] = {0, 0}; public void sort(NewArrayList vect) { Deque stack = new ArrayDeque(); first = 0; last = vect.size() - 1; stack.push(new Integer[] {first, last}); while(!stack.isEmpty()) { sortStep(vect, stack); } } private void sortStep(NewArrayList vect, Deque stack) { // initialize indices temp = stack.pop(); first = temp[0]; last = temp[1]; boundLo = first; boundHi = last; pivot = last; while(first = 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[] {pivot + 1, boundHi}); } } 

ArrayList是这种排序的最佳集合吗？

 public class NewArrayList extends ArrayList { public NewArrayList() { super(); } public void swap(int index1, int index2) { this.set(index1, this.set(index2, this.get(index1))); } } 

考虑到建议后修改后的代码

 public class QuickSort  { private int first, last, boundLo, boundHi, pivot; int temp[] = {0, 0}; public QuickSort() { super(); } public void sort(List list) { Deque stack = new ArrayDeque(); first = 0; last = list.size() - 1; stack.push(new int[] {first, last}); while(!stack.isEmpty()) { sortStep(list, stack); } } private void sortStep(List list, Deque stack) { temp = stack.pop(); first = temp[0]; last = temp[1]; boundLo = first; boundHi = last; pivot = last; while(first = 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[] {pivot + 1, boundHi}); } } 

Answer 1

 public class Sort { /** Returns a sorted list of attributes. */ protected int[] sortAttributes1(int[] array) { Queue queue = new ArrayDeque(); 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; } }