Javaは高速ソート再帰と非再帰を実現
1730 ワード
//
public static void QuickSort(long[] numbers, int l, int h) {
int i;
if (l < h) {
i = Hoare(numbers, l, h);
QuickSort(numbers, 1, i - 1);
QuickSort(numbers, i + 1, h);
}
}
static class Part {
int low;
int high;
public Part(int low, int high) {
this.low = low;
this.high = high;
}
}
//
public static void QuickSort2(long[] numbers) {
int size = numbers.length;
int low = 0, high = size - 1;
int i;
Stack stact = new Stack<>();
int tag = 1;
do {
while (low < high) {
i = Hoare(numbers, low, high);
Part part = new Part(i + 1, high);
stact.push(part);
high = i - 1;
}
if (stact.isEmpty()) {
tag = 0;
} else {
Part part = stact.pop();
low = part.low;
high = part.high;
}
} while (tag == 1);
}
public static int Hoare(long[] numbers, int low, int high) {
long x = numbers[low];
while (low < high) {
while (low == x) {
high--;
}
if (low < high) {
numbers[low] = numbers[high];
low++;
}
while (low < high && numbers[low] <= x) {
low++;
}
if (low < high) {
numbers[high] = numbers[low];
high--;
}
}
numbers[low] = x;
return low;
}