-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathsort_marge.html
134 lines (129 loc) · 4.65 KB
/
sort_marge.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
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<title>归并排序</title>
</head>
<body>
<canvas height="820" id="canvas1" style="background:white;" width="800"></canvas>
<script>
// 动画延时
const DELAY = 100;
// 生成数组长度
const ARR_LENGTH = 50;
// 保存排序记录
const STATUS_ARR = [];
const RESULT_DATA = {
// 待排序数组
arr: [],
// 当前正在合并的索引-开始位置
margeIndexStart: -1,
// 当前正在合并的索引-中间位置
margeIndexMiddle: -1,
// 当前正在合并的索引-结束位置
margeIndexEnd: -1,
// 正在对比的索引
comparingIndex: [],
// 已对比结束的索引
compared: [],
// 对比结束的索引插入位置
insertedIndex: [],
};
function draw(canvas, data) {
let context = canvas.getContext('2d');
let maxHeight = canvas.getAttribute('height');
let width = canvas.getAttribute('width');
let w = width / data.arr.length;
context.clearRect(0, 0, 800, 820);
for (let i = 0; i < data.arr.length; i++) {
if (data.insertedIndex.indexOf(i) !== -1) {
context.fillStyle = 'orange';
} else if (i >= data.margeIndexStart && i < data.margeIndexEnd) {
context.fillStyle = 'lightGray';
} else {
context.fillStyle = 'blue';
}
context.fillRect(i * w, maxHeight / 2 - data.arr[i], w - 1, data.arr[i]);
}
if (data.tempArr) {
for (let i = 0; i < data.tempArr.length; i++) {
if (data.compared.indexOf(i) !== -1) {
context.fillStyle = 'white';
} else if (data.comparingIndex.indexOf(i) !== -1) {
context.fillStyle = 'pink';
} else if (i >= data.margeIndexStart && i < data.margeIndexMiddle) {
context.fillStyle = 'Aqua';
} else if (i >= data.margeIndexMiddle && i < data.margeIndexEnd) {
context.fillStyle = 'LightCyan';
} else {
context.fillStyle = 'white';
}
context.fillRect(i * w, maxHeight - data.tempArr[i], w - 1, data.tempArr[i]);
}
}
}
function margeSort(arr, start, length) {
if (start >= length - 1) {
return;
}
let middle = Math.floor((start + length) / 2);
margeSort(arr, start, middle);
margeSort(arr, middle, length);
marge(arr, start, middle, length);
}
function marge(arr, start, middle, length) {
RESULT_DATA.compared = [];
RESULT_DATA.insertedIndex = [];
RESULT_DATA.margeIndexStart = start;
RESULT_DATA.margeIndexMiddle = middle;
RESULT_DATA.margeIndexEnd = length;
// 备份数组,用于显示高度
RESULT_DATA.tempArr = RESULT_DATA.arr.slice();
STATUS_ARR.push(JSON.parse(JSON.stringify(RESULT_DATA)));
let arr1 = arr.slice(start, middle);
let arr2 = arr.slice(middle, length);
arr1.push(Infinity);
arr2.push(Infinity);
let i = j = 0;
for (let k = start; k < length; k++) {
RESULT_DATA.comparingIndex = [start + i, middle + j];
STATUS_ARR.push(JSON.parse(JSON.stringify(RESULT_DATA)));
if (arr1[i] <= arr2[j]) {
RESULT_DATA.compared.push(start + i);
arr[k] = arr1[i++];
} else {
RESULT_DATA.compared.push(middle + j);
arr[k] = arr2[j++];
}
RESULT_DATA.comparingIndex = [];
RESULT_DATA.insertedIndex.push(k);
STATUS_ARR.push(JSON.parse(JSON.stringify(RESULT_DATA)));
}
RESULT_DATA.margeIndexStart = undefined;
RESULT_DATA.margeIndexMiddle = undefined;
RESULT_DATA.margeIndexEnd = undefined;
STATUS_ARR.push(JSON.parse(JSON.stringify(RESULT_DATA)));
}
function run(id) {
let canvas = document.getElementById(id);
if (!canvas) {
return false;
}
// 生成随机数组
for (let i = 0; i < ARR_LENGTH; i++) {
RESULT_DATA.arr.push(Math.floor(Math.random() * 400 + 1));
}
margeSort(RESULT_DATA.arr, 0, RESULT_DATA.arr.length);
// STATUS_ARR.push(JSON.parse(JSON.stringify(RESULT_DATA)));
let i = 0;
setInterval(() => {
if (i < STATUS_ARR.length) {
draw(canvas, STATUS_ARR[i]);
i++;
}
}, DELAY);
}
run('canvas1');
</script>
</body>
</html>