いつも忘れる
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.Random;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
public class QuickSort {
private static void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
private static int partition(int[] arr, int l, int r) {
// l <= x < r
int n = r - l;
// 3 4 7 5 2 8 9 6
// l r
Random random = new Random(System.nanoTime());
int pivot = random.nextInt(n) + l;
// 3 4 7 5 2 8 9 6
// l ^ r
swap(arr, pivot, r - 1); // move to right
// 3 4 7 6 2 8 9 5
// l ^ r
// 3 4 7 6 2 8 9 5
// ^ ... t
// 3 4 7 6 2 8 9 5
// ^
// 3 4 7 6 2 8 9 5
// ^
// 3 4 2 6 7 8 9 5
// ^
int t = l;
for (int i = l; i < r - 1; i++) {
if (arr[i] <= arr[r - 1]) {
if (i != t) {
swap(arr, i, t);
}
t++;
}
}
// 3 4 2 5 7 8 9 6
// ^
swap(arr, r - 1, t);
return t + 1; // pivot値以上となる部分配列の左端
}
public static void qsort(int[] arr, int l, int r) {
// ↓を出力するとわかりやすい
// System.out.println(l + "<= x <" + r + " in " + Arrays.toString(arr));
// l <= x < r
if (r - l <= 1) return; // 要素数が1以下の場合はソート済みなので終了
int index = partition(arr, l, r);
qsort(arr, l, index); // pivot値以下となる部分配列
qsort(arr, index, r); // pivot値以上となる部分配列
}
public static void main(String[] args) {
List<Integer> list = IntStream.range(0, 1000).mapToObj(Integer::valueOf).collect(Collectors.toList());
Collections.shuffle(list);
int[] arr = list.stream().mapToInt(Integer::intValue).toArray();
qsort(arr, 0, arr.length);
System.out.println(Arrays.toString(arr));
}
}