高速ソートの非再帰表現java
1184 ワード
今日はふとスタックを見て、どうやってクイックソートを非再帰的に整理すればいいか考えて、一日かけて書きました.
皆さんのご指摘を歓迎します
public int[] quickSort(int[] num) {
if (num.length < 3)
return null;
int start = 0;
int end = num.length - 1;
int middle = 0;
Stack<Integer> index = new Stack<Integer>();
index.push(start);
index.push(end);
while (!index.isEmpty()) {
end = index.pop();
start = index.pop();
int i = start;
int j = end;
int pivot = num[i]; // ,
while (i < j) {
while (i < j && num[j] >= pivot)
// , , ,
j--;
num[i] = num[j];
while (i < j && num[i] <= pivot)
// , , 。
i++;
num[j] = num[i];
}
num[i] = pivot;
middle = i;
if (middle - 1 > start) {
index.push(start);
index.push(middle - 1);
}
if (middle + 1 < end) {
index.push(middle + 1);
index.push(end);
}
}
return num;
}
皆さんのご指摘を歓迎します