使用 JavaScript 实现排序算法（第一部分）
我最近一直在学习数据结构和算法，在阅读过程中我注意到，用 JavaScript 实现算法的例子并不多。大多数例子都是用 Java、Python、C、C++ 等语言写的。也许人们更倾向于使用这些语言而不是 JavaScript 是有原因的？我不太确定。
在第一部分中，我将展示三种排序算法的 JavaScript 实现：
- 归并排序
- 插入排序
- 冒泡排序
本文并非旨在深入解释算法的工作原理及其性能。如果您想了解更多相关信息，我找到了一篇不错的参考资料：排序算法。
为了简单起见，我将对一个list只有 5 个元素的简单列表进行排序[4, 2, 3, 1, 5]。
归并排序
归并排序采用分治法对数组元素进行排序。简单来说，它不是将整个数组作为一个整体来处理，而是不断地将数组分成两半，直到两半都排序完毕，然后将这两半合并成一个完整的列表。
视觉的
代码
function mergeSort(list) {
const len = list.length
// an array of length == 1 is technically a sorted list
if (len == 1) {
return list
}
// get mid item
const middleIndex = Math.ceil(len / 2)
// split current list into two: left and right list
let leftList = list.slice(0, middleIndex)
let rightList = list.slice(middleIndex, len)
leftList = mergeSort(leftList)
rightList = mergeSort(rightList)
return merge(leftList, rightList)
}
// Solve the sub-problems and merge them together
function merge(leftList, rightList) {
const sorted = []
while (leftList.length > 0 && rightList.length > 0) {
const leftItem = leftList[0]
const rightItem = rightList[0]
if (leftItem > rightItem) {
sorted.push(rightItem)
rightList.shift()
} else {
sorted.push(leftItem);
leftList.shift()
}
}
// if left list has items, add what is left to the results
while (leftList.length !== 0) {
sorted.push(leftList[0])
leftList.shift()
}
// if right list has items, add what is left to the results
while (rightList.length !== 0) {
sorted.push(rightList[0])
rightList.shift()
}
// merge the left and right list
return sorted
}
const list = [4, 2, 3, 1, 5]
const sorted = mergeSort(list)
console.log(sorted)
插入排序
插入排序算法一次处理一个元素，逐步构建最终的有序列表。它通过以下步骤实现：每次取出一个元素，将其与列表中的其他元素进行比较，找到它的正确位置，然后将其放入该位置。
这被称为基于比较的排序。
视觉的
代码
function insertionSort(list) {
const len = list.length
for (let i = 1; i < len; i++)
{
if (list[i] < list[0])
{
// move current element to the first position
list.unshift(list.splice(i,1)[0])
}
else if (list[i] > list[i-1])
{
// maintain element position
continue
}
else {
// find where element should go
for (let j = 1; j < i; j++) {
if (list[i] >= list[j-1] && list[i] <= list[j])
{
// move element
list.splice(j, 0, list.splice(i,1)[0])
}
}
}
}
return list
}
const list = [4, 2, 3, 1, 5]
const sorted = insertionSort(list)
console.log(sorted)
冒泡排序
冒泡排序是另一种基于比较的排序算法，它比较列表中的每一对元素，如果它们顺序错误，则交换它们，直到列表排序完成。
视觉的
代码
function bubbleSort(list)
{
let swapped
let n = list.length-1
do {
swapped = false
for (let i=0; i < n; i++)
{
// compare pairs of elements
// if left element > right element, swap
if (list[i] > list[i+1])
{
const temp = list[i]
list[i] = list[i+1]
list[i+1] = temp
swapped = true
}
}
}
// continue swapping until sorted
while (swapped)
return list
}
const list = [4, 2, 3, 1, 5]
const sorted = bubbleSort(list)
console.log(sorted)
就是这样！😊 如果你好奇的话，我用的是这个网站来制作图片的。
接下来，我将介绍：
- 快速排序
- 堆排序
- 计数排序