排序算法可视化工具 - 冒泡排序、插入排序、希尔排序、选择排序、快速排序、归并排序、堆排序、计数排序、桶排序、基数排序
<!DOCTYPE html>
<html>
<head>
<style>
.container {
display: flex;
justify-content: center;
align-items: center;
height: 100vh;
flex-direction: column;
}
<pre><code>.sort-animation {
display: flex;
justify-content: center;
align-items: center;
width: 400px;
height: 200px;
border: 1px solid #000;
font-size: 24px;
margin-bottom: 20px;
}
.sort-animation div {
height: 100%;
display: flex;
align-items: flex-end;
}
.bar {
width: 20px;
background-color: #000;
margin: 0 1px;
}
button {
padding: 10px 20px;
font-size: 18px;
margin: 5px;
}
</code></pre>
</style>
</head>
<body>
<div class="container">
<select id="algorithmSelector">
</select>
<div class="sort-animation"></div>
<div>
<button id="prevButton" disabled>上一步</button>
<button id="nextButton" disabled>下一步</button>
<button id="explanationButton">解释</button>
</div>
</div>
<script>
// 冒泡排序
function bubbleSort(arr) {
let len = arr.length;
for (let i = 0; i < len - 1; i++) {
for (let j = 0; j < len - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
let temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
return arr;
}
// 插入排序
function insertionSort(arr) {
let len = arr.length;
for (let i = 1; i < len; i++) {
let key = arr[i];
let j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
return arr;
}
// 希尔排序
function shellSort(arr) {
let len = arr.length;
let gap = Math.floor(len / 2);
while (gap > 0) {
for (let i = gap; i < len; i++) {
let temp = arr[i];
let j = i;
while (j >= gap && arr[j - gap] > temp) {
arr[j] = arr[j - gap];
j = j - gap;
}
arr[j] = temp;
}
gap = Math.floor(gap / 2);
}
return arr;
}
// 选择排序
function selectionSort(arr) {
let len = arr.length;
for (let i = 0; i < len - 1; i++) {
let minIndex = i;
for (let j = i + 1; j < len; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
let temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
return arr;
}
// 快速排序
function quickSort(arr, low, high) {
if (low < high) {
let pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
return arr;
}
function partition(arr, low, high) {
let pivot = arr[high];
let i = low - 1;
for (let j = low; j < high; j++) {
if (arr[j] < pivot) {
i++;
let temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
let temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return i + 1;
}
// 归并排序
function mergeSort(arr) {
let len = arr.length;
if (len <= 1) {
return arr;
}
let mid = Math.floor(len / 2);
let left = arr.slice(0, mid);
let right = arr.slice(mid);
return merge(mergeSort(left), mergeSort(right));
}
function merge(left, right) {
let result = [];
let lLen = left.length;
let rLen = right.length;
let l = 0;
let r = 0;
while (l < lLen && r < rLen) {
if (left[l] < right[r]) {
result.push(left[l++]);
} else {
result.push(right[r++]);
}
}
return result.concat(left.slice(l)).concat(right.slice(r));
}
// 堆排序
function heapSort(arr) {
let len = arr.length;
for (let i = Math.floor(len / 2) - 1; i >= 0; i--) {
heapify(arr, len, i);
}
for (let i = len - 1; i > 0; i--) {
let temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
heapify(arr, i, 0);
}
return arr;
}
function heapify(arr, len, i) {
let largest = i;
let l = 2 * i + 1;
let r = 2 * i + 2;
if (l < len && arr[l] > arr[largest]) {
largest = l;
}
if (r < len && arr[r] > arr[largest]) {
largest = r;
}
if (largest !== i) {
let temp = arr[i];
arr[i] = arr[largest];
arr[largest] = temp;
heapify(arr, len, largest);
}
}
// 计数排序
function countingSort(arr) {
let len = arr.length;
let output = [];
let count = [];
let max = Math.max(...arr);
for (let i = 0; i <= max; i++) {
count[i] = 0;
}
for (let i = 0; i < len; i++) {
count[arr[i]]++;
}
for (let i = 1; i <= max; i++) {
count[i] += count[i - 1];
}
for (let i = len - 1; i >= 0; i--) {
output[count[arr[i]] - 1] = arr[i];
count[arr[i]]--;
}
return output;
}
// 桶排序
function bucketSort(arr, bucketSize = 5) {
if (arr.length === 0) {
return arr;
}
let min = Math.min(...arr);
let max = Math.max(...arr);
let bucketCount = Math.floor((max - min) / bucketSize) + 1;
let buckets = new Array(bucketCount);
for (let i = 0; i < bucketCount; i++) {
buckets[i] = [];
}
for (let i = 0; i < arr.length; i++) {
let bucketIndex = Math.floor((arr[i] - min) / bucketSize);
buckets[bucketIndex].push(arr[i]);
}
arr.length = 0;
for (let i = 0; i < bucketCount; i++) {
insertionSort(buckets[i]);
for (let j = 0; j < buckets[i].length; j++) {
arr.push(buckets[i][j]);
}
}
return arr;
}
// 基数排序
function radixSort(arr) {
let max = Math.max(...arr);
let maxLength = String(max).length;
let buckets = new Array(10);
for (let i = 0; i < 10; i++) {
buckets[i] = [];
}
for (let i = 0; i < maxLength; i++) {
for (let j = 0; j < arr.length; j++) {
let digit = Math.floor(arr[j] / Math.pow(10, i)) % 10;
buckets[digit].push(arr[j]);
}
arr.length = 0;
for (let j = 0; j < 10; j++) {
for (let k = 0; k < buckets[j].length; k++) {
arr.push(buckets[j][k]);
}
buckets[j] = [];
}
}
return arr;
}
// 排序算法对象
const sortingAlgorithms = {
'冒泡排序': {
data: [5, 1, 4, 2, 8],
steps: [
[0, 1],
[1, 2],
[2, 3],
[3, 4],
[0, 1],
[1, 2],
[2, 3],
[0, 1],
[1, 2],
[0, 1]
],
explanation: '冒泡排序是一种简单的排序算法，它重复地遍历要排序的列表，比较相邻的元素，并将它们交换位置以确保较大的元素总是移动到列表的末尾。'
},
'插入排序': {
data: [5, 1, 4, 2, 8],
steps: [
[1, 0],
[2, 1, 0],
[3, 2, 1, 0],
[4, 3, 2, 1, 0]
],
explanation: '插入排序是一种排序算法，它通过将元素逐个插入到已排序的子列表中来排序列表。'
},
'希尔排序': {
data: [5, 1, 4, 2, 8],
steps: [
[1, 3],
[2, 4],
[0, 2],
[1, 3],
[2, 4],
[0, 2],
[1, 3],
[0, 2],
[1, 3],
[0, 1]
],
explanation: '希尔排序是一种排序算法，它通过将元素分成多个子列表并对子列表进行排序来排序列表。'
},
'选择排序': {
data: [5, 1, 4, 2, 8],
steps: [
[0, 1],
[0, 2],
[0, 3],
[0, 4],
[1, 2],
[1, 3],
[1, 4],
[2, 3],
[2, 4],
[3, 4]
],
explanation: '选择排序是一种排序算法，它通过在未排序的子列表中找到最小（或最大）元素，并将它与子列表的第一个元素交换位置来排序列表。'
},
'快速排序': {
data: [5, 1, 4, 2, 8],
steps: [
[4, 0, 1, 2, 3],
[1, 0, 2, 3, 4],
[2, 0, 1, 3, 4],
[0, 1, 2, 3, 4],
[3, 2, 1, 0, 4],
[2, 1, 0, 3, 4],
[1, 0, 2, 3, 4],
[0, 1, 2, 3, 4]
],
explanation: '快速排序是一种排序算法，它通过选择一个枢轴元素，并将小于枢轴元素的元素移到枢轴元素的左边，并将大于枢轴元素的元素移到枢轴元素的右边来排序列表。'
},
'归并排序': {
data: [5, 1, 4, 2, 8],
steps: [
[0, 1, 2, 3, 4],
[0, 1, 2, 3, 4],
[0, 1, 2, 3, 4],
[0, 1, 2, 3, 4],
[0, 1, 2, 3, 4],
[0, 1, 2, 3, 4],
[0, 1, 2, 3, 4],
[0, 1, 2, 3, 4],
[0, 1, 2, 3, 4],
[0, 1, 2, 3, 4]
],
explanation: '归并排序是一种排序算法，它通过将列表递归地分成两个子列表，并对子列表进行排序，然后将排序后的子列表合并成一个排序的列表来排序列表。'
},
'堆排序': {
data: [5, 1, 4, 2, 8],
steps: [
[0, 1, 2, 3, 4],
[0, 1, 2, 3, 4],
[0, 1, 2, 3, 4],
[0, 1, 2, 3, 4],
[0, 1, 2, 3, 4],
[0, 1, 2, 3, 4],
[0, 1, 2, 3, 4],
[0, 1, 2, 3, 4],
[0, 1, 2, 3, 4],
[0, 1, 2, 3, 4]
],
explanation: '堆排序是一种排序算法，它通过将列表建造成一个堆，然后重复地从堆中取出最大（或最小）元素，并将它放到列表的末尾来排序列表。'
},
'计数排序': {
data: [5, 1, 4, 2, 8],
steps: [
[0, 1, 2, 3, 4],
[0, 1, 2, 3, 4],
[0, 1, 2, 3, 4],
[0, 1, 2, 3, 4],
[0, 1, 2, 3, 4],
[0, 1, 2, 3, 4],
[0, 1, 2, 3, 4],
[0, 1, 2, 3, 4],
[0, 1, 2, 3, 4],
[0, 1, 2, 3, 4]
],
explanation: '计数排序是一种排序算法，它通过计算每个元素出现的次数，然后根据计数结果将元素放到排序后的列表中来排序列表。'
},
'桶排序': {
data: [5, 1, 4, 2, 8],
steps: [
[0, 1, 2, 3, 4],
[0, 1, 2, 3, 4],
[0, 1, 2, 3, 4],
[0, 1, 2, 3, 4],
[0, 1, 2, 3, 4],
[0, 1, 2, 3, 4],
[0, 1, 2, 3, 4],
[0, 1, 2, 3, 4],
[0, 1, 2, 3, 4],
[0, 1, 2, 3, 4]
],
explanation: '桶排序是一种排序算法，它通过将元素分成多个桶，然后对每个桶进行排序，最后将排序后的桶合并成一个排序的列表来排序列表。'
},
'基数排序': {
data: [5, 1, 4, 2, 8],
steps: [
[0, 1, 2, 3, 4],
[0, 1, 2, 3, 4],
[0, 1, 2, 3, 4],
[0, 1, 2, 3, 4],
[0, 1, 2, 3, 4],
[0, 1, 2, 3, 4],
[0, 1, 2, 3, 4],
[0, 1, 2, 3, 4],
[0, 1, 2, 3, 4],
[0, 1, 2, 3, 4]
],
explanation: '基数排序是一种排序算法，它通过将元素的位从低位到高位进行排序，然后将排序后的位合并成一个排序的列表来排序列表。'
}
};
const animationSpeed = 100; // 动画速度（毫秒）
let currentStep = 0; // 当前步骤
let currentAlgorithm = null; // 当前排序算法
let animationInterval = null; // 动画间隔
const sortAnimationContainer = document.querySelector('.sort-animation');
const prevButton = document.getElementById('prevButton');
const nextButton = document.getElementById('nextButton');
const explanationButton = document.getElementById('explanationButton');
// 创建排序动画
function createSortAnimation(arr) {
sortAnimationContainer.innerHTML = '';
for (let i = 0; i < arr.length; i++) {
const bar = document.createElement('div');
bar.style.height = arr[i] * 2 + 'px';
bar.classList.add('bar');
sortAnimationContainer.appendChild(bar);
}
}
// 开始排序动画
function startSortAnimation() {
prevButton.disabled = true;
nextButton.disabled = true;
explanationButton.disabled = true;
currentStep = 0;
animationInterval = setInterval(animateSort, animationSpeed);
}
// 动画排序
function animateSort() {
if (currentStep >= currentAlgorithm.steps.length) {
clearInterval(animationInterval);
prevButton.disabled = false;
nextButton.disabled = false;
explanationButton.disabled = false;
return;
}
const step = currentAlgorithm.steps[currentStep];
const bars = sortAnimationContainer.children;
for (let i = 0; i < bars.length; i++) {
bars[i].style.backgroundColor = '#000';
}
for (let i = 0; i < step.length; i++) {
bars[step[i]].style.backgroundColor = 'red';
}
currentStep++;
}
// 显示解释
function showExplanation() {
alert(currentAlgorithm.explanation);
}
// 上一步
function prevStep() {
if (currentStep > 0) {
currentStep--;
animateSort();
}
}
// 下一步
function nextStep() {
if (currentStep < currentAlgorithm.steps.length) {
animateSort();
currentStep++;
}
}
// 监听按钮点击事件
prevButton.addEventListener('click', prevStep);
nextButton.addEventListener('click', nextStep);
explanationButton.addEventListener('click', showExplanation);
// 选择排序算法
function selectAlgorithm() {
const selectedAlgorithm = document.getElementById('algorithmSelector').value;
currentAlgorithm = sortingAlgorithms[selectedAlgorithm];
createSortAnimation(currentAlgorithm.data);
}
// 初始化
function init() {
const algorithmSelector = document.getElementById('algorithmSelector');
for (const algorithm in sortingAlgorithms) {
const option = document.createElement('option');
option.value = algorithm;
option.text = algorithm;
algorithmSelector.appendChild(option);
}
algorithmSelector.addEventListener('change', selectAlgorithm);
selectAlgorithm();
}
init();
</script>
</body>
</html>
原文地址: http://www.cveoy.top/t/topic/qtWu 著作权归作者所有。请勿转载和采集!