在线体验
设计思路
1. 排序算法部分
快速排序的思想就是在序列中选择一个支点pivot, 让小于pivot的元素放在它的左边，不小于（说大于的话不准确）它的元素放在它的右边。
visualgo.net 的实现，维护三个序列，s1, s2, unknown
s1中存放小于的元素，s2中存放不小于支点的元素，unknown是未排序序列（具体的区分在动画中很清楚）
function partition(a, i, j) {
let m = i, p = a[i];
for (let k = i + 1; k <= j; k++) {
if (a[k] < p) {
m++;
swap(a, m, k);
}
}
swap(a, m, i);
return m;
}
function quickSort(a, low, high) {
if (low < high) {
int m = partition(a, low, high);
quickSort(a, low, m - 1);
quickSort(a, m + 1, high);
}
}
2. 动画部分
排序的每一步操作存储在未来发生的回调函数执行队列中，全局变量 step 代表操作步数
假设每一步动画时延为1s，
那么在未来的0s, 1s, 2s, ..., step * 1s 将会在页面上看到具体的排序操作，
如果没有CSS的过渡效果，那么整个过程将会显得十分生硬。
例如我将第一个节点的位置与第3个节点的位置交换，
在 0s - 1s 有一段时间间隔，设置 transiton: all 1s 就能看到过渡效果。
完整代码
<script
>
let step
= 0;
let nodeList
= document
.getElementsByClassName('num'),
reloadBtn
= document
.querySelector('.reload'),
sortBtn
= document
.querySelector('.sort');
let initColor
= 'rgb(173, 216, 230)',
sortedColor
= 'rgb(255, 165, 0)',
pivoColor
= 'rgb(255, 255, 0)',
s1Color
= 'rgb(60, 179, 113)',
s2Color
= 'rgb(153, 50, 204)',
activeColor
= 'rgb(220, 20, 60)';
let colorMap
= {
'sorted': sortedColor
,
's1': s1Color
,
's2': s2Color
,
'init': initColor
,
'pivo': pivoColor
,
'active': activeColor
};
let showConsoleNode
= document
.querySelector('.showConsole');
let arr
= [], timeout
= 0.4, queue
= [];
function handleChange() {
let selectOps
= document
.querySelector('#speed-control');
let selectIdx
= selectOps
.selectedIndex
;
let val
= selectOps
.options
[selectIdx
].value
;
timeout
= Number(val
);
console
.log(timeout
)
}
function swapPosition(node1
, node2
) {
[node1
.style
.left
, node2
.style
.left
] = [node2
.style
.left
, node1
.style
.left
];
}
function setBgColor(nodeArr
, color
) {
for (let i
= 0; i
< nodeArr
.length
; i
++) {
nodeArr
[i
].style
.background
= color
;
}
}
function swap(arr
, i
, j
) {
[arr
[i
], arr
[j
]] = [arr
[j
], arr
[i
]];
}
function createFrameForChangeColor(arr
, step
, nodeType
) {
setTimeout(() => {
console
.log('select:' + arr
[0].innerText
);
setBgColor(arr
, colorMap
[nodeType
]);
}, step
* timeout
* 1.6 * 1000);
}
function createFrameForSwapPos(node1
, node2
, step
) {
setTimeout(() => {
console
.log(`swap ${node1.innerText}, ${node2.innerText}`);
swapPosition(node1
, node2
)
}, step
* timeout
* 1.6 * 1000)
}
function resetColorForPartOfArr(arr
, l
, r
, m
, step
) {
setTimeout(() => {
for (let i
= l
; i
<= r
; i
++) {
let node
= nodeList
[arr
[i
].nodeIndex
];
if (i
!== m
) {
setBgColor([node
], initColor
);
} else {
setBgColor([node
], sortedColor
);
}
}
}, step
* timeout
* 1.6 * 1000);
}
function resetColorForAll(step
) {
setTimeout(() => {
for (let i
= 0; i
< nodeList
.length
; i
++) {
let node
= nodeList
[arr
[i
].nodeIndex
];
setBgColor([node
], initColor
);
}
}, step
* timeout
* 1.6 * 1000);
}
function partition(a
, i
, j
) {
let m
= i
, p
= a
[i
];
createFrameForChangeColor([nodeList
[a
[i
].nodeIndex
]], step
++, 'pivo');
for (let k
= i
+ 1; k
<= j
; k
++) {
createFrameForChangeColor([nodeList
[a
[k
].nodeIndex
]], step
++, 'active');
if (a
[k
].val
< p
.val
) {
m
++;
createFrameForChangeColor([nodeList
[a
[k
].nodeIndex
]], step
++, 's1');
createFrameForSwapPos(nodeList
[a
[m
].nodeIndex
], nodeList
[a
[k
].nodeIndex
], step
++);
swap(a
, m
, k
);
} else {
createFrameForChangeColor([nodeList
[a
[k
].nodeIndex
]], step
++, 's2')
}
}
createFrameForSwapPos(nodeList
[a
[m
].nodeIndex
], nodeList
[a
[i
].nodeIndex
], step
++);
swap(a
, m
, i
);
resetColorForPartOfArr(arr
, i
, j
, m
, step
++);
return m
;
}
function quickSort(a
, low
, high
) {
if (low
<= high
) {
let m
= partition(a
, low
, high
);
quickSort(a
, low
, m
- 1);
quickSort(a
, m
+ 1, high
);
}
}
function init() {
let fragment
= document
.createDocumentFragment();
for (let i
= 0; i
< 10; i
++) {
let div
= document
.createElement('div'),
num
= parseInt(Math
.random() * 10 + 1);
arr
.push({
val
: num
,
nodeIndex
: i
,
});
div
.className
= 'num';
div
.style
.height
= `${num * 20}px`;
div
.style
.left
= `${i * 50}px`;
div
.style
.bottom
= '0';
div
.style
.background
= initColor
;
div
.style
.transition
= `left ${timeout}s, background ${timeout * 0.6}s`;
div
.innerText
= num
;
fragment
.append(div
);
}
document
.querySelector('.animate-contanier').append(fragment
);
}
function reload() {
arr
= [];
for (let i
= 0; i
< 10; i
++) {
let div
= nodeList
[i
],
num
= parseInt(Math
.random() * 10 + 1);
arr
.push({
val
: num
,
nodeIndex
: i
,
});
div
.style
.left
= `${i * 50}px`;
div
.style
.bottom
= '0';
div
.style
.height
= `${num * 20}px`;
div
.innerText
= num
;
}
}
init();
document
.querySelector('.sort').addEventListener('click', function () {
quickSort(arr
, 0, 9, 0);
resetColorForAll(step
)
})
</script
>
