JavaScript实现的九种排序算法
本文将详细介绍JavaScript实现的九种排序算法，包括了冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序、堆排序、计数排序和桶排序。每种算法的实现都会提供示例代码以及详细的注释和讲解，帮助读者更好地理解排序算法的实现过程。
冒泡排序
冒泡排序是一种简单的排序算法，它重复地走访过要排序的元素，依次比较相邻两个元素的大小，并交换那些顺序错误的元素，直到没有任何一对数字需要比较。
以下是JavaScript实现的冒泡排序的示例代码：
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;
}
console.log(bubbleSort([5, 3, 8, 4, 2]));
// 输出结果为 [2, 3, 4, 5, 8]
在这个例子中，我们定义了一个名为bubbleSort的函数，它接受一个数组作为输入，并返回排序后的数组。该函数使用了两个嵌套的for循环，用于比较相邻两个元素的大小并交换它们的位置，直到数组被完全排序。
选择排序
选择排序是一种简单的排序算法，它每次从未排序的数组中选择最小的元素，将它存放在数组的起始位置，然后将剩余的元素再次进行选择排序。
以下是JavaScript实现的选择排序的示例代码：
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;
}
console.log(selectionSort([5, 3, 8, 4, 2]));
// 输出结果为 [2, 3, 4, 5, 8]
在这个例子中，我们定义了一个名为selectionSort的函数，它接受一个数组作为输入，并返回排序后的数组。该函数使用了两个for循环，用于选择数组中的最小元素，并将它存放在数组的起始位置。
插入排序
插入排序是一种简单的排序算法，它将待排序的元素插入到已排好序的子序列中，直到整个数组都被排序。
以下是JavaScript实现的插入排序的示例代码：
function insertionSort(arr) {
let len = arr.length;
for (let i = 1; i < len; i++) {
let current = arr[i];
let j = i - 1;
while (j >= 0 && arr[j] > current) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = current;
}
return arr;
}
console.log(insertionSort([5, 3, 8, 4, 2]));
// 输出结果为 [2, 3, 4, 5, 8]
在这个例子中，我们定义了一个名为insertionSort的函数，它接受一个数组作为输入，并返回排序后的数组。该函数使用了一个for循环和一个while循环，用于将待排序的元素插入到已排好序的子序列中。
希尔排序
希尔排序是一种基于插入排序的排序算法，它将待排序的元素进行分组，每组进行插入排序，完成之后逐渐减小分组大小，最后全部完成插入排序。
以下是JavaScript实现的希尔排序的示例代码：
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 -= gap;
}
arr[j] = temp;
}
gap = Math.floor(gap / 2);
}
return arr;
}
console.log(shellSort([5, 3, 8, 4, 2]));
// 输出结果为 [2, 3, 4, 5, 8]
在这个例子中，我们定义了一个名为shellSort的函数，它接受一个数组作为输入，并返回排序后的数组。该函数使用了一个while循环和两个for循环，用于将待排序的元素进行分组并进行插入排序。
归并排序
归并排序是一种非常高效的排序算法，它将两个已排序的数组合并为一个更大的已排序数组。
以下是JavaScript实现的归并排序的示例代码：
function mergeSort(arr) {
if (arr.length < 2) {
return arr;
}
let middle = Math.floor(arr.length / 2);
let left = arr.slice(0, middle);
let right = arr.slice(middle);
return merge(mergeSort(left), mergeSort(right));
}
function merge(left, right) {
let result = [];
while (left.length && right.length) {
if (left[0] <= right[0]) {
result.push(left.shift());
} else {
result.push(right.shift());
}
}
while (left.length) {
result.push(left.shift());
}
while (right.length) {
result.push(right.shift());
}
return result;
}
console.log(mergeSort([5, 3, 8, 4, 2]));
// 输出结果为 [2, 3, 4, 5, 8]
在这个例子中，我们定义了两个函数，mergeSort和merge。mergeSort函数将待排序的数组进行分解，直到每个部分都只有一个元素，然后调用merge函数将这些部分合并为一个已排序的数组。
快速排序
快速排序是一种常用的排序算法，它通过选择一个基准元素，将数组分成两个子数组，分别对这两个子数组进行排序，然后将两个子数组合并为一个已排序的数组。
以下是JavaScript实现的快速排序的示例代码：
function quickSort(arr) {
if (arr.length < 2) {
return arr;
}
let pivotIndex = Math.floor(Math.random() * arr.length);
let pivot = arr[pivotIndex];
let left = [];
let right = [];
for (let i = 0; i < arr.length; i++) {
if (i === pivotIndex) {
continue;
}
if (arr[i] < pivot) {
left.push(arr[i]);
} else {
right.push(arr[i]);
}
}
return [...quickSort(left), pivot, ...quickSort(right)];
}
console.log(quickSort([5, 3, 8, 4, 2]));
// 输出结果为 [2, 3, 4, 5, 8]
在这个例子中，我们定义了一个名为quickSort的函数，它接受一个数组作为输入，并返回排序后的数组。该函数通过选择一个基准元素将数组分成两个较小的子数组，并递归地对这两个子数组进行排序。
堆排序
堆排序是一种基于二叉堆的排序算法，它将待排序的元素存放在一棵完全二叉树上，并按照某种规则将它们进行排序。
以下是JavaScript实现的堆排序的示例代码：
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 left = 2 * i + 1;
let right = 2 * i + 2;
if (left < len && arr[left] > arr[largest]) {
largest = left;
}
if (right < len && arr[right] > arr[largest]) {
largest = right;
}
if (largest !== i) {
let temp = arr[i];
arr[i] = arr[largest];
arr[largest] = temp;
heapify(arr, len, largest);
}
}
console.log(heapSort([5, 3, 8, 4, 2]));
// 输出结果为 [2, 3, 4, 5, 8]
在这个例子中，我们定义了一个名为heapSort的函数，它接受一个数组作为输入，并返回排序后的数组。该函数通过 hepify 函数将待排序的元素存放在一棵完全二叉树上，并逐步将其排序。
计数排序
计数排序是一种比较高效的排序算法，它通过统计待排序数组中每个元素出现的次数，然后对待排序元素进行排序。
以下是JavaScript实现的计数排序的示例代码：
function countingSort(arr) {
let maxValue = Math.max(...arr);
let bucket = new Array(maxValue + 1).fill(0);
let sortedIndex = 0;
arr.forEach(item => {
bucket[item]++;
});
bucket.forEach((item, index) => {
while (item > 0) {
arr[sortedIndex++] = index;
item--;
}
});
return arr;
}
console.log(countingSort([5, 3, 8, 4, 2]));
// 输出结果为 [2, 3, 4, 5, 8]
在这个例子中，我们定义了一个名为countingSort的函数，它接受一个数组作为输入，并返回排序后的数组。该函数通过统计待排序数组中每个元素出现的次数，并按照次数对待排序元素进行排序。
桶排序
桶排序是一种比较高效的排序算法，它将待排序元素分到不同的桶中，对每个桶中的元素进行排序，然后将它们全部合并为一个已排序数组。
以下是JavaScript实现的桶排序的示例代码：
function bucketSort(arr, bucketSize = 5) {
if (arr.length === 0) {
return arr;
}
let minValue = arr[0];
let maxValue = arr[0];
for (let i = 1; i < arr.length; i++) {
if (arr[i] < minValue) {
minValue = arr[i];
} else if (arr[i] > maxValue) {
maxValue = arr[i];
}
}
let bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1;
let buckets = [];
for (let i = 0; i < bucketCount; i++) {
buckets[i] = [];
}
for (let i = 0; i < arr.length; i++) {
buckets[Math.floor((arr[i] - minValue) / bucketSize)].push(arr[i]);
}
arr.length = 0;
for (let i = 0; i < buckets.length; i++) {
insertionSort(buckets[i]);
for (let j = 0; j < buckets[i].length; j++) {
arr.push(buckets[i][j]);
}
}
return arr;
}
console.log(bucketSort([5, 3, 8, 4, 2]));
// 输出结果为 [2, 3, 4, 5, 8]
在这个例子中，我们定义了一个名为bucketSort的函数，它接受一个数组作为输入，并返回排序后的数组。该函数将待排序元素放到不同的桶中，对每个桶中的元素进行排序，并将它们全部合并为一个已排序数组。
结论
本文介绍了JavaScript实现的九种排序算法，分别是冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序、堆排序、计数排序和桶排序。这些算法各具特点，适用于不同的排序场景。读者可以根据自己的需求选择合适的算法。
本站文章如无特殊说明，均为本站原创，如若转载，请注明出处：JavaScript实现的九种排序算法 - Python技术站
微信扫一扫 
支付宝扫一扫 