非递归QuickSort

本文介绍了非递归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; } }