1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71
| function swap(
array: any[] | Int8Array | Uint8Array | Uint8ClampedArray | Int16Array |
Uint16Array | Int32Array | Uint32Array | Float32Array | Float64Array,
idx1: number,
idx2: number,
): void {
const tmp = array[idx1];
array[idx1] = array[idx2];
array[idx2] = tmp;
}
function select(
array: Int8Array | Uint8Array | Uint8ClampedArray | Int16Array |
Uint16Array | Int32Array | Uint32Array | Float32Array | Float64Array,
first: number,
nth: number,
last: number,
comp: (a: number, b: number) => boolean,
): void;
function select<T>(
array: T[],
first: number,
nth: number,
last: number,
comp: (a: T, b: T) => boolean,
): void;
function select<T>(
array: Int8Array | Uint8Array | Uint8ClampedArray | Int16Array |
Uint16Array | Int32Array | Uint32Array | Float32Array | Float64Array |
T[],
first: number,
nth: number,
last: number,
comp: (a: number | T, b: number | T) => boolean,
): void {
--last;
while (first < last) {
if (last - first > 600) {
const n = last - first + 1;
const m = nth - first + 1;
const z = Math.log(n);
const s = 0.5 * Math.exp(2 * z / 3);
const sd = 0.5 * Math.sqrt(z * s * (n - s) / n) * (m - n / 2 < 0 ? -1 : 1);
const newFirst = Math.max(first, Math.floor(nth - m * s / n + sd));
const newLast = Math.min(last, Math.floor(nth + (n - m) * s / n + sd));
select(array, newFirst, nth, newLast, comp);
}
const t = array[nth];
let i = first;
let j = last;
swap(array, first, nth);
if (comp(t, array[last])) swap(array, first, last);
while (i < j) {
swap(array, i++, j--);
while (comp(array[i], t)) ++i;
while (comp(t, array[j])) --j;
}
if (!comp(array[first], t)) {
swap(array, first, j);
} else {
swap(array, ++j, last);
}
if (j <= nth) first = j + 1;
if (nth <= j) last = j - 1;
}
} |