-
Notifications
You must be signed in to change notification settings - Fork 10
/
BFPRT.html
82 lines (71 loc) · 2.49 KB
/
BFPRT.html
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
72
73
74
75
76
77
78
79
80
81
82
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<title>BFPRT</title>
</head>
<body>
<!--引入swap-->
<script src="../Sort/SortTestHelper.js"></script>
<script>
function main(arr, k) {
let kIndex = BFPRT(arr, 0, arr.length - 1, k);
console.log(`第${k}大元素所在索引:${kIndex}`);
console.log(`第${k}大元素${arr[kIndex]}`);
console.log(`排序后数组:[${arr}]`);
}
// 个人见解:相对单路快排的优化版,以arr[0]作为对比元素,避免极端情况(队列头为极大或极小元素)造成的时间复杂度退化,
// 每组排序后寻找中位数,把所有中位数集合再次寻找中位数,此时这个二次寻找后的中位数相对整个数组来说接近于排序后数组的中位数
function BFPRT(arr, l, r, k) {
let central_index = getCentralIndex(arr, l, r),
boundary_index = partition(arr, l, r, central_index),
num = boundary_index - l + 1;
if (num === k) {
return boundary_index
} else if (num > k) {
return BFPRT(arr, l, boundary_index - 1, k)
} else {
return BFPRT(arr, boundary_index + 1, r, k - num)
}
}
function insertSort(arr, l, r) {
for (let i = l + 1; i <= r; i++) {
let el = arr[i],
j;
for (j = i; j > l && arr[j - 1] < el; j--) {
arr[j] = arr[j - 1];
}
arr[j] = el
}
return l + ((r - l) >> 1)
}
function getCentralIndex(arr, l, r) {
if (r - l < 4) {
return insertSort(arr, l, r)
}
let sub_right = l - 1,
index;
for (let i = l; i + 4 <= r; i += 5) {
index = insertSort(arr, i, i + 4);
sub_right++;
[arr[sub_right], arr[index]] = [arr[index], arr[sub_right]]
}
return BFPRT(arr, l, sub_right, (sub_right - l >> 1) + 1)
}
function partition(arr, l, r, central_index) {
[arr[l], arr[central_index]] = [arr[central_index], arr[l]];
let j = l,
el = arr[l];
for (let i = l + 1; i <= r; i++) {
if (arr[i] > el) {
j++;
[arr[j], arr[i]] = [arr[i], arr[j]]
}
}
[arr[l], arr[j]] = [arr[j], arr[l]];
return j
}
main([32, 153, 100, -50, -10, 6, 5, 1356, 20, 160, 2, 1432, 4, 50, 14, 102, -30, 3, 45, 1312, 1, -1, -3], 5)
</script>
</body>
</html>