数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究使用 JavaScript 实现插入排序以按升序对数字数组进行排序
在编程领域，数组排序的技巧至关重要，因为它允许高效地组织和操作数据。在实现可靠的排序算法时，插入排序成为了一种用途广泛且有效的选择。本文深入探讨了 JavaScript 的复杂世界，探索了实现插入排序以按升序排列数字数组的过程。通过理解该算法的底层机制并利用 JavaScript 强大的功能，开发人员可以释放高效排序和组织数值数据的能力，从而提高应用程序的性能和可用性。
问题陈述
手头的挑战涉及使用 JavaScript 实现插入排序算法的任务，目的是按升序排列数字数组。主要目标是设计一个程序，智能地重新排列给定数组的元素，确保每个后续元素根据其数值相对于先前元素放置在正确的位置。例如，假设我们提供了一个数组
[9, 2, 7, 4, 1]
执行插入排序算法后，预期结果将是一个符合升序排列的数组，例如
[1, 2, 4, 7, 9]
方法
在本文中，我们将了解多种使用 JavaScript 解决上述问题陈述的方法：
基本插入排序
二分插入排序
递归插入排序
方法 1：基本插入排序
基本插入排序算法在数组中维护一个已排序的子数组。从第二个元素开始，每个元素都与子数组中的前一个元素进行比较，如果较小则向右移动。此过程持续进行，直到找到正确的位置并将元素插入。此过程对所有元素重复，从而得到一个完全排序的数组。
示例
insertionSort 函数以数组 arr 作为输入，并使用插入排序算法返回已排序的数组。它从第二个元素开始迭代，将其存储在 current 变量中。一个 while 循环将当前元素与已排序子数组中的前一个元素进行比较，并将较大的元素向右移动。循环持续进行，直到到达数组的开头或找到一个较小的元素。然后将当前元素插入到已排序子数组中的正确位置。此过程对所有元素重复，从而得到一个已排序的数组。
function insertionSort(arr) {
for (let i = 1; i < arr.length; 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;
}
const arr = [9, 2, 7, 4, 1];
console.log(insertionSort(arr));
输出
以下是控制台输出：
[ 1, 2, 4, 7, 9 ]
方法 2：二分插入排序
二分插入排序算法通过在已排序的子数组中利用二分查找来确定每个元素的正确位置，从而提高了基本插入排序的效率。它不是线性搜索，而是通过将当前元素与子数组的中间元素进行比较并相应地调整搜索边界来执行二分查找。一旦确定了插入点，则将右侧的元素向右移动以腾出空间，并将当前元素插入。此过程对所有元素重复，从而得到一个完全排序的数组。
示例
binaryInsertionSort 函数以数组 arr 作为输入，并使用二分插入排序算法返回已排序的数组。它从第二个元素开始迭代，假设第一个元素已排序。当前元素存储在 current 变量中。该算法在已排序的子数组中执行二分查找，以通过将其与中间元素进行比较并调整搜索边界来找到当前元素的正确位置。找到位置后，该算法将元素向右移动，并将当前元素插入到正确的位置。此过程对所有元素重复，从而得到一个已排序的数组。
function binaryInsertionSort(arr) {
for (let i = 1; i < arr.length; i++) {
let current = arr[i];
let left = 0;
let right = i - 1;
while (left <= right) {
let mid = Math.floor((left + right) / 2);
if (current < arr[mid]) {
right = mid - 1;
} else {
left = mid + 1;
}
}
for (let j = i - 1; j >= left; j--) {
arr[j + 1] = arr[j];
}
arr[left] = current;
}
return arr;
}
const arr = [9, 2, 7, 4, 1];
console.log(binaryInsertionSort(arr));
输出
以下是控制台输出：
[ 1, 2, 4, 7, 9 ]
方法 3：递归插入排序
递归插入排序算法是插入排序的递归版本，使用递归来排序数组。对于大小为 1 或更小的子数组，它认为它们已经排序。对于较大的子数组，它递归调用自身以排序不包含最后一个元素的子数组。递归调用返回并且子数组已排序后，该算法将最后一个元素放置到已排序子数组中的正确位置。这是通过将最后一个元素与已排序子数组中的元素进行比较并在必要时将其向右移动来实现的。此过程重复进行，直到所有元素都插入到其正确的位置，从而得到一个完全排序的数组。
示例
recursiveInsertionSort 函数递归地将插入排序算法应用于输入数组。它检查数组是否已排序，如果已排序则返回它。否则，它递归调用自身处理大小为 n - 1 的子数组。递归调用之后，该函数使用 while 循环将最后一个元素与已排序子数组中的元素进行比较。如果一个元素较大，则将其向右移动。此过程持续进行，直到循环到达数组的开头或找到一个较小的元素。最后，将最后一个元素插入到正确的位置。此过程对所有元素重复，从而得到一个已排序的数组。
function recursiveInsertionSort(arr, n = arr.length) {
if (n <= 1) return arr;
recursiveInsertionSort(arr, n - 1);
let last = arr[n - 1];
let j = n - 2;
while (j >= 0 && arr[j] > last) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = last;
return arr;
}
const arr = [9, 2, 7, 4, 1];
console.log(recursiveInsertionSort(arr));
输出
以下是控制台输出：
[ 1, 2, 4, 7, 9 ]
结论
最后，使用 JavaScript 实现插入排序算法以按升序排列数字数组对于寻求熟练排序方法的开发人员来说是一个明智的选择。通过迭代地将元素放置到其适当的位置，该算法展示了一种明智的方法来组织数值数据。虽然插入排序可能不如其他排序技术广为人知，但其效率和简单性使其在某些情况下成为宝贵的工具。在 JavaScript 中使用此算法使开发人员能够在他们的编码库中使用一个鲜为人知但功能强大的工具，从而得到简化和排序的数组。总之，在 JavaScript 中利用插入排序算法的力量对于那些在数组排序工作中寻求精确和优雅的人来说是一个奇幻的努力。
1K+ 阅读量
